Word Ladder

题目：

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

Only one letter can be changed at a time

Each intermediate word must exist in the dictionary

Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.

分析：

这个题目有几个关键点

1. 首先，给你unordered_set肯定不是用来loop through的，希望你用的是find()
因此，只能loop每个word的各个digit并且对每个digit来loop其他25各字母
2. 注意到上面说的是loop through 25个字母，也就是说当oldChar == c的时候不做
3. 这是个bfs记次的问题，所以需要用int size和for循环来控制
4. 每次在dict中find之后，要删除这条dict记录，以避免循环，这个超级超级重要
5. 上来先做dict.erase(start)

解法：

class Solution {
public:
    /**
      * @param start, a string
      * @param end, a string
      * @param dict, a set of string
      * @return an integer
      */
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        // write your code here
        if (start == end) {
            return 1;
        }
        if (start.size() == 0 || end.size() == 0 || dict.size() == 0) {
            return 0;
        }
        dict.erase(start);
        int stepCount = 1;
        queue<string> Q;
        Q.push(start);
        while (!Q.empty() ) {
            int size = Q.size();
            stepCount++;
            for (int s = 0; s < size; s++) {
                string word = Q.front();
                Q.pop();
                for (int i = 0; i < word.size(); i++) {
                    char oldChar = word[i];
                    for (char c = 'a'; c < 'z'; c++) {
                        if (c == oldChar) {
                            continue;
                        }
                        word[i] = c;
                        if (word == end) {
                            return stepCount;
                        }
                        if (dict.find(word) != dict.end() ) {
                            Q.push(word);
                            dict.erase(word);
                        }
                    }
                    word[i] = oldChar;
                }
            }
        }
        return stepCount;
    }
};