Word Ladder

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

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

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

Solution: The trick is to generate all possible words after transformation (there are 25*len possible words, since all letter is in small , and utilize the O(1) search for hash table. Since if the dictionary is large, it is not efficient to traverse the entire dictionary.  

Then the classic BFS should be efficient enough for this problem. The following code passes LeetCode Online Large Judge.

class Solution {
public:
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        queue<pair<string, int> > path;
        unordered_set<string> mark;
        int len = 1;
        string chk;
        char tmp;
        path.push(make_pair(start, 1));
        mark.insert(start);
        while(!path.empty()) {
            chk = path.front().first;
            len = path.front().second;
            path.pop();
            for(int i = 0; i < chk.length(); ++i) {
                tmp = chk[i];
                for(int j = 0; j < 26; ++j) {
                    if(tmp != 'a' + j) {
                        chk[i] = 'a' + j;
                        if(chk == end) return len + 1;
                        else if(dict.find(chk) != dict.end() && 
                        mark.find(chk) == mark.end()) {
                            path.push(make_pair(chk, len + 1));
                            mark.insert(chk);
                        }
                    }
                }
                chk[i] = tmp;
            }
        }
        return 0;
    }
};