Word Ladder
Problem Statement
A transformation sequence from word beginWord to word endWord using a dictionary
wordList
is a sequence of words beginWord -> s_1 -> s_2 -> ... -> s_k
such that:
- Every adjacent pair of words differs by a single letter.
- Every
s_i
for1 <= i <= k
is inwordList
. Note that beginWord does not need to be inwordList
. s_k == endWord
Given two words, beginWord
and endWord
, and a dictionary wordList
, return the number of words in the shortest transformation sequence from beginWord
to endWord
, or 0 if no such sequence exists.
Solution
class Solution {
public:
int getDiff(string a, string b) {
int diff = 0;
for (int i = 0; i < max(a.size(), b.size()); i++) {
if (i < a.size() && i < b.size()) {
if (a[i] != b[i]) diff++;
} else {
diff++;
}
}
return diff;
}
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
int n = wordList.size();
// vector<bool> seen(n, false);
unordered_set<string> unusedWords;
for (const auto s: wordList) {
if (s != beginWord) unusedWords.insert(s);
}
vector<string> seq;
queue<pair<string, int>> q;
q.push({beginWord, 1});
while (!q.empty()) {
auto t = q.front();
q.pop();
string a = t.first;
int stage = t.second;
// while (seq.size() >= stage) {
// seq.pop_back();
// }
// seq.push_back({ a });
vector<string> matchingWords;
for (auto s: unusedWords) {
if (getDiff(a, s) == 1) {
if (s == endWord) {
// for (auto p: seq) {
// cout << p << "\n";
// }
// cout << s << "\n";
return stage + 1;
} else {
matchingWords.push_back(s);
}
}
}
for (const string s: matchingWords) {
q.push({s, stage + 1});
unusedWords.erase(s);
}
}
return 0;
}
};