Given two words (beginWord and endWord), and a dictionary, find the length of shortest transformation sequence from beginWord to endWord, 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.

//What if beginword == endWord? return 1
//What if beginword can be transformed to endWord by one step? return 2
//All are lower letters

class Solution {
public:
    int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
        unordered_map<string, int> visited;
        wordList.insert(endWord);
        queue<pair<string, int> >q;
        q.push(make_pair(beginWord, 1));
        visited[beginWord] = 1;
        while(!q.empty()){
            string word = q.front().first;
            int dis = q.front().second;
            q.pop();
            if(word == endWord) return dis;
            vector<string> neighbors = findNeighbors(word, wordList, visited);
            for(int i = 0; i < neighbors.size(); i++){
                q.push(make_pair(neighbors[i], dis + 1));
                visited[neighbors[i]] = 1;
            }
        }
        return 0;
    }
    vector<string> findNeighbors(string word, unordered_set<string>& wordList, unordered_map<string, int>& visited){
        vector<string> ans;
        for(int i = 0; i < word.size(); i++){
            for(int j = 0; j < 26; j++){
                if(j + 'a' == word[i]) continue;
                string tmp = word;
                tmp[i] = j + 'a';
                if(wordList.find(tmp) != wordList.end() && visited.find(tmp) == visited.end()){
                    ans.push_back(tmp);
                }
            }
        }
        return ans;
    }
    
};

Dijkstra algorithm, compute the shortest path between two nodes in a given graph.

There is a tricky thing here. Since the wordDict would be very large, it’s costly to traverse it every time when we want to find an adjacent node in the graph. We test each possible step by change one letter in the string at one time. The time complexity is o(26 * lengthOfWord).

Hash table dict is used to store visited node.

class Solution {
public:
    int distance;
    bool isFinish, isFound;
    int ladderLength(string beginWord, string endWord, unordered_set<string>& wordDict) {
        queue<string> q;
        unordered_map<string, int> dict;
        string lastNode = beginWord;
        distance = 1;
        isFinish = false;
        isFound = false;
        if(beginWord == endWord){
            return 1;
        }
        q.push(beginWord);
        dict[beginWord] = 1;
        while(isFinish == false){
            if(q.empty()){
                break;
            }
            string word = q.front();
            q.pop();
            if (canMove(word, endWord)){
                isFound = true;
                isFinish = true;
                distance++;
                break;
            }
            for(int i = 0; i < word.size(); i++){
                for(char c = 'a'; c <= 'z'; c++){
                    if(word[i] == c) continue;
                    string tmps = word;
                    tmps[i] = c;
                    if(wordDict.find(tmps) != wordDict.end() && dict.find(tmps) == dict.end()){
                        q.push(tmps);
                        dict[tmps] = 1;
                    }
                }    
            }
            if(word == lastNode){
                distance++;
                lastNode = q.back();
            }
        }
        if(isFound == true){
            return distance;
        }
        else{
            return 0;
        }
    }
    bool canMove(string a, string b){
        int diff = 0;
        for(int i = 0; i < a.size(); i++){
            if(a[i] == b[i]){
                continue;
            }    
            else{
                diff++;
            }
        }
        if(diff == 1){
            return true;
        }
        else{
            return false;
        }
    }
};