LeetCode 127 Word Ladder
概述
https://leetcode.com/problems/word-ladder/
动态规划法 + 回溯
实现的时候注意:
- 让求得是字梯的长度,不是转换的次数,需要 + 1;
- endWord 可能不存在;
有 bug 的解法(44 / 50 test cases passed):
class Solution {
public:
unordered_map<string, int> m;
int ladderLength(string& beginWord, string& endWord, vector<string>& wordList) {
bool existed = false;
for (auto& w : wordList) {
if (w == endWord) {
existed = true;
break;
}
}
if (!existed) return 0;
vector<bool> used(wordList.size(), false);
int ans = helper(beginWord, endWord, wordList, used);
if (ans == INT_MAX) return 0;
else return ans + 1;
}
int helper(string& beginWord, string& endWord, vector<string>& wordList, vector<bool>& used) {
// if (beginWord == endWord) return 0;
if (isValid(beginWord, endWord)) return 1;
if (m.count(beginWord)) return m[beginWord];
int ans = INT_MAX;
for (int i = 0; i < wordList.size(); i ++) {
if (used[i] || wordList[i] == beginWord) continue;
if (isValid(beginWord, wordList[i])) {
used[i] = true;
int future = helper(wordList[i], endWord, wordList, used);
// cout << beginWord << " choose " << wordList[i] << " future " << future << endl;
used[i] = false;
if (future != INT_MAX) {
ans = min(ans, 1 + future);
}
}
}
m[beginWord] = ans;
return ans;
}
bool isValid(string& a, string& b) {
if (a.size() != b.size()) return false;
bool used = false;
for (int i = 0; i < a.size(); i ++) {
if (a[i] == b[i]) continue;
if (used) return false;
used = true;
}
return used;
}
};
宽度优先搜索
https://leetcode.com/problems/word-ladder/discuss/40707/C%2B%2B-BFS
TLE 了(34 / 50 test cases passed):
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> dict(wordList.begin(), wordList.end());
queue<string> todo;
todo.push(beginWord);
int ladder = 1;
while (!todo.empty()) {
int sz = todo.size();
while (sz--) {
auto c = todo.front(); todo.pop();
if (c == endWord) return ladder;
dict.erase(c);
for (auto iter = dict.begin(); iter != dict.end(); iter ++) {
if (isValid(c, *iter)) {
todo.push(*iter);
}
}
}
ladder ++;
}
return 0;
}
bool isValid(string& a, string b) {
if (a.size() != b.size()) return false;
bool used = false;
for (int i = 0; i < a.size(); i ++) {
if (a[i] == b[i]) continue;
if (used) return false;
used = true;
}
return used;
}
};
当字典很长时,遍历字典不如遍历一个单词的所有可能组成方式(起码是常量,虽然大了点):
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> dict(wordList.begin(), wordList.end());
queue<string> todo;
todo.push(beginWord);
int ladder = 1;
while (!todo.empty()) {
int sz = todo.size();
while (sz--) {
auto word = todo.front(); todo.pop();
if (word == endWord) return ladder;
dict.erase(word);
for (int i = 0; i < word.size(); i ++) {
char c = word[i];
for (int j = 0; j < 26; j ++) {
word[i] = 'a' + j;
if (dict.count(word)) todo.push(word);
}
word[i] = c;
}
}
ladder ++;
}
return 0;
}
};
然而还是 TLE 了:50 / 50 test cases passed, but took too long.
注意哦,上面的实现中,我们可能会 erase 一个 key 多次,但是没关系,erase 可以处理不存在的 key, 实际上其返回了一个值用来指示 erase 了多少 key。
不慌,这个时候我们只需要冷静分析再提交一次就好了,AC 了哦耶。
Links: leetcode-127-word-ladder