diff options
Diffstat (limited to 'word_ladder2.cpp')
-rw-r--r-- | word_ladder2.cpp | 47 |
1 files changed, 0 insertions, 47 deletions
diff --git a/word_ladder2.cpp b/word_ladder2.cpp deleted file mode 100644 index 12cff05..0000000 --- a/word_ladder2.cpp +++ /dev/null @@ -1,47 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - vector<vector<string>> findLadders(string beginWord, string endWord, - vector<string> &wordList) { - unordered_map<string, int> um; - vector<vector<string>> ans; - for (const auto w : wordList) - um.insert({w, INT_MAX}); - um[beginWord] = 0; - queue<pair<string, vector<string>>> qpv; - qpv.push({beginWord, {beginWord}}); - while (!qpv.empty()) { - auto n = qpv.front(); - qpv.pop(); - string w = n.first; - auto v = n.second; - if (w == endWord) - ans.push_back(v); - continue; - for (int i = 0; i < w.size(); i++) { - string t = w; - for (char c = 'a'; c <= 'z'; c++) { - t[i] = c; - if (t == w) - continue; - if (um.find(t) == um.end()) - continue; - if (um[t] < v.size()) - continue; - um[t] = v.size(); - v.push_back(t); - qpv.push({t, v}); - v.pop_back(); - } - } - } - return ans; - } -}; - -int main() { - Solution obj; - string beginWord = "hit", endWord = "cog"; - vector<string> wordList = {"hot", "dot", "dog", "lot", "log", "cog"}; -} |