127. Word Ladder

bfs O(nm)

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> s(begin(wordList), end(wordList));
        queue<string> q{{beginWord}};
        s.erase(beginWord); // 如果beginWord在字典里则将其删去
        int res = 1;
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                auto w = q.front(); q.pop();
                if (w == endWord) return res;
                for (char &c : w) {
                    auto t = c;
                    for (char x = 'a'; x <= 'z'; ++x) {
                        c = x;
                        if (!s.count(w) || t == x) continue;
                        s.erase(w);
                        q.push(w);
                    }
                    c = t;
                }
            }
            ++res;
        }
        return 0;
    }
};

bfs O(nm) n是单词个数 m是单词平均长度

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        queue<string> q;
        q.push(beginWord);
        int res = 0;
        while (!q.empty()) {
            ++res;
            int n = q.size();
            for (int i = 0; i < n; ++i) {
                auto w = q.front();
                q.pop();
                if (w == endWord) return res;
                int m = wordList.size();
                for (int j = 0; j < m; ++j) {
                    while (j < m && isSimilar(w, wordList[j])) {
                        q.push(wordList[j]);
                        swap(wordList[j], wordList[m - 1]);
                        wordList.pop_back();
                        --m;
                    }
                }
            }
        }
        return 0;
    }

    bool isSimilar(const string &s1, const string &s2) {
        int cnt = 0;
        int n = s1.length();
        for (int i = 0; i < n; ++i) {
            cnt += (s1[i] != s2[i]);
            if (cnt > 1) break;
        }
        return cnt == 1;
    }
};