aboutsummaryrefslogtreecommitdiff
path: root/word_ladder2.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'word_ladder2.cpp')
-rw-r--r--word_ladder2.cpp47
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"};
-}