Word Ladder

Word Ladder

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

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

class Solution {
public:
    int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
        vector<string> words(1, beginWord);
        int n = beginWord.size();
        int icount = 1;
        while ( ! wordList.empty() ) {
            int nword = words.size();
            vector<string> tmp;
            for ( int i = 0; i <= nword-1; i++ ) {
                for ( int j = 0; j <= n-1; j++ ) {
                    for ( auto letter: "abcdefghijklmnopqrstuvwxyz" ) {
                        if ( letter == words[i][j] ) continue;
                        string newWord = words[i].substr(0, j) + letter + words[i].substr(j+1);
                        if ( newWord == endWord ) return icount += 1;
                        if ( wordList.find(newWord) != wordList.end() ) {
                            tmp.push_back(newWord);
                            wordList.erase(wordList.find(newWord));
                        }
                    }
                }
            }
            if ( tmp.size() == 0 ) return 0;
            words = tmp;
            icount += 1;
        }
        return 0;
    }
};

Notes
BFS:
for a given word,

• check all the possible "next word" (by substituting any letter by any other letter);
  • If the "next word" is the ending word, then it is a valid transformation
• put all the valid "next word" into a vector, and remove those words from wordList.
  • If the vector is empty, it means that there is not valid transformation.
• scan the new vector of words until the wordList is empty.
• Note if we once used up all the word and jump out of the loop, it means that there's no valid transformation.

Word Ladder II

Given:

beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Solution
This solution keep getting "TLE" error for the large test case? Compare with other solutions online!

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
        vector<vector<string>> words;
        vector<vector<string>> res;
        vector<string> begin(1, beginWord);
        words.push_back(begin);
        if ( wordList.find(beginWord) != wordList.end() ) wordList.erase(wordList.find(beginWord));
        if ( wordList.find(endWord) != wordList.end() ) wordList.erase(wordList.find(endWord));
        int n = beginWord.size();
        bool hasFound = false;
        while ( true ) {
            int nword = words.size();
            vector<vector<string>> tmp;
            unordered_set<string> del;
            for ( int i = 0; i <= nword-1; i++ ) {
                vector<string> strs = words[i];
                string s = strs[strs.size()-1];
                for ( int j = 0; j <= n-1; j++ ) {
                    for ( auto letter: "abcdefghijklmnopqrstuvwxyz" ) {
                        if ( letter == s[j] ) continue;
                        string newWord = s.substr(0, j) + letter + s.substr(j+1);
                        if ( wordList.find(newWord) != wordList.end() ) {
                            strs = words[i];
                            strs.push_back(newWord);
                            tmp.push_back(strs);
                            del.insert(newWord);
                        }
                        if ( newWord == endWord ) {
                            strs = words[i];
                            strs.push_back(newWord);
                            res.push_back(strs);
                            hasFound = true;
                        }
                    }
                }
            }
            if ( int(tmp.size()) == 0 ) break;
            if ( hasFound ) break;
            for ( auto it = del.begin(); it != del.end(); it++ ) wordList.erase(wordList.find(*(it)));
            words = tmp;
        }
        return res;
    }
};