Word Ladder

<-H 127> Word Ladder

// Method 1
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        int flag = 0;
        for(auto &it : wordList) {
            if(endWord == it) {
                flag = 1;
                break;
            }
        }
        if(!flag)
            return 0;
        map<string,vector<string>> m;
        wordList.push_back(beginWord);
        for(int i = 0; i < wordList.size(); i++) {
            for(int j = 0; j < wordList[i].size(); j++) {
                string res = wordList[i];
                res[j] = '*';
                m[res].push_back(wordList[i]);
            }
        }
        map<string,int>vis;
        queue<string>q;
        q.push(beginWord);
        int count = 0;
        while(!q.empty()) {
            int size = q.size();
            count++;
            for(int i = 0; i < size; i++) {
                string res = q.front();
                if(res == endWord)
                    return count;
                q.pop();

                // if(vis[res])continue;
                for(int j = 0; j < res.size(); j++) {
                    string pattern = res;
                    pattern[j] = '*';
                    for(auto &it : m[pattern]) {
                        if(vis[it])
                            continue;
                        else {
                            vis[it] = 1;
                            q.push(it);
                        }
                    }
                }
            }
        }
        return 0;
    }
};

// Method 2
class Solution {
public:

    int BBFS(unordered_set<string> &dictionary,
             int length,
             unordered_set<string> &beginSet,
             unordered_set<string> &endSet,
             unordered_set<string> &workingSet) {
        workingSet.clear();
        int n = beginSet.begin()->size();

        for(auto &i : beginSet)
            dictionary.erase(i);

        for(auto &word : beginSet) {
            for(int i = 0; i < n; i++) {
                string newWord = word;
                for(char c = 'a'; c <= 'z'; c++) {
                    newWord[i] = c;
                    if(dictionary.count(newWord)) {
                        if(endSet.count(newWord))
                            return length+1;
                        workingSet.insert(newWord);
                    }
                }
            }
        }

        if(workingSet.size() == 0)
            return 0;

        if(endSet.size() < workingSet.size())
            return BBFS(dictionary, length+1, endSet, workingSet, beginSet);

        return BBFS(dictionary, length+1, workingSet, endSet, beginSet);
    }

    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dictionary(wordList.begin(), wordList.end());

        if(dictionary.count(endWord) == 0)

            return 0;

        unordered_set<string> beginSet;
        beginSet.insert(beginWord);

        unordered_set<string> endSet;
        endSet.insert(endWord);

        unordered_set<string> workingSet;

        return BBFS(dictionary, 1, beginSet, endSet, workingSet);
    }
};