127. Word Ladder - CPP - Solution


  • 0
    Y
    // https://leetcode.com/problems/word-ladder/
    #include <iostream>
    #include <deque>
    #include <string>
    #include <vector>
    #include <unordered_set>
    #include <unordered_map>
    using namespace std;
    class Solution {
    public:
        int ladderLength(const string& beginWord, const string& endWord, const unordered_set<string>& wordList) {
            int result(0);
            unordered_set<string> List(wordList);
            List.insert(beginWord);
            List.insert(endWord);
            unordered_map<string, unordered_set<string> > Graph;
            unordered_map<string, string> ChildToParent;
            deque<string> dq;
            for(const auto& i : List) {
                for(size_t j = 0; j < i.size(); ++j) {
                    for(size_t k = 0; k < 26; ++k) {
                        string str(i);
                        str[j] = 'a' + k;
                        if (str != i) {
                            if (List.count(str)) {
                                Graph[i].insert(str);
                            }
                        }
                    }
                }
            }
            dq.push_back(beginWord);
            while (true) {
                if (dq.empty()) {
                    break;
                }
                for(const auto& i : Graph[dq.front()]) {
                    if (!ChildToParent.count(i)) {
                        ChildToParent[i] = dq.front();
                        dq.push_back(i);
                    }
                }
                dq.pop_front();
            }
            if (ChildToParent.count(endWord)) {
                result = 1;
                string it(endWord);
                while (true) {
                    if (it == beginWord) {
                        break;
                    }
                    else if (it != beginWord) {
                        ++result;
                        it = ChildToParent[it];
                    }
                }
            }
            return result;
        }
    };
    int main(int argc, char** argv) {
        Solution solution;
        string beginWord("hit");
        string endWord("cog");
        unordered_set<string> wordList({"hot","dot","dog","lot","log"});
        cout << solution.ladderLength(beginWord, endWord, wordList) << '\n';
        return 0;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.