// 双向BFS 使用queue 128ms
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_map<string, unordered_set<string>> dict;
bool isEndWordInDict = false;
for (auto &word: wordList) {
if (word == endWord) isEndWordInDict = true;
for (int i = 0; i < word.size(); ++i) {
string s = word;
s[i] = '*';
dict[s].insert(word);
}
}
if (!isEndWordInDict) return 0;
queue<string> begWords({beginWord}), endWords({endWord});
unordered_set<string> begVisited;
unordered_set<string> endVisited;
begVisited.insert(beginWord);
endVisited.insert(endWord);
int count = 1;
while(!begWords.empty() && !endWords.empty()) {
count++;
if (begWords.size() > endWords.size()) {
swap(begWords, endWords);
swap(begVisited, endVisited);
}
for (int k = begWords.size(); k > 0; --k) {
string cur = begWords.front();
begWords.pop();
begVisited.insert(cur);
for (int i = 0; i < cur.size(); ++i) {
string t = cur;
t[i] = '*';
if (dict.count(t)) {
for (auto it = dict[t].begin(); it != dict[t].end(); ++it) {
if (!begVisited.count(*it)) {
begVisited.insert(*it);
if (endVisited.count(*it)) {
return count;
} else {
begWords.push(*it);
}
}
}
}
}
}
}
return 0;
}
};
// 双向BFS 212 ms
class Solution {
unordered_map<string, unordered_set<string>> dict;
unordered_set<string> begWords;
unordered_set<string> endWords;
unordered_set<string> begVisited;
unordered_set<string> endVisited;
unordered_set<string> next;
int count = 1;
bool bfs(unordered_set<string>& src, unordered_set<string>& dst, unordered_set<string>& visited) {
count++;
while(!src.empty()) {
auto it = src.begin();
string s = *it;
visited.insert(s);
// cout << s << endl;
for (int i = 0; i < s.size(); ++i) {
string t = s;
t[i] = '*';
if (dict.count(t)) {
for (auto it = dict[t].begin(); it != dict[t].end(); ++it) {
if (!visited.count(*it)) {
// cout << "!" << *it << endl;
visited.insert(*it);
if (dst.count(*it)) {
return true;
} else {
next.insert(*it);
}
}
}
}
}
src.erase(it);
}
src = next;
next.clear();
return false;
}
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
bool isEndWordInDict = false;
for (auto &word: wordList) {
if (word == endWord) isEndWordInDict = true;
for (int i = 0; i < word.size(); ++i) {
string s = word;
s[i] = '*';
dict[s].insert(word);
}
}
if (!isEndWordInDict) return 0;
begWords = {beginWord};
endWords = {endWord};
bool flag = true;
while(!begWords.empty() && !endWords.empty()) {
if (flag) {
if (bfs(begWords, endWords, begVisited)) return count;
}
else {
if (bfs(endWords, begWords, endVisited)) return count;
}
flag = !flag;
}
return 0;
}
};
// 单向BFS 268 ms
// hashset优化
// 单向BFS
class Solution {
unordered_map<string, unordered_set<string>> dict;
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
bool isEndWordInDict = false;
for (auto &word: wordList) {
if (word == endWord) isEndWordInDict = true;
for (int i = 0; i < word.size(); ++i) {
string s = word;
s[i] = '*';
dict[s].insert(word);
}
}
if (!isEndWordInDict) return 0;
unordered_set<string> visited;
unordered_set<string> begWords = {beginWord};
unordered_set<string> endWords = {endWord};
unordered_set<string> nextBeg;
unordered_set<string> nextEnd;
int count = 1;
while(!begWords.empty() && !endWords.empty()) {
count++;
while(!begWords.empty()) {
auto it = begWords.begin();
string s = *it;
visited.insert(s);
for (int i = 0; i < s.size(); ++i) {
string t = s;
t[i] = '*';
if (dict.count(t)) {
for (auto it = dict[t].begin(); it != dict[t].end(); ++it) {
if (!visited.count(*it)) {
visited.insert(*it);
if (endWords.count(*it)) {
return count;
} else {
nextBeg.insert(*it);
}
}
}
}
}
begWords.erase(it);
}
begWords = nextBeg;
nextBeg.clear();
}
return 0;
}
};
/*
// 单向BFS 超时, 通过33/43
class Solution {
inline bool transform(string &src, string &dst) {
int count = 0;
for (int i = 0; i < src.size(); ++i) {
count += src[i] != dst[i] ? 1 : 0;
if (count > 1) break;
}
// cout << src << ":" << dst << " res:" << int(count == 1) << endl;
return count == 1;
}
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> us;
for (auto &word: wordList) {
us.insert(word);
}
if (!us.count(endWord)) return 0;
vector<string> words = {endWord};
vector<string> nextWords;
int count = 1, res = INT_MAX;
us.clear();
while(!words.empty()) {
// for (auto &word: words) cout << word << ","; cout << endl;
count++;
for (auto &curWord: words) {
if (transform(curWord, beginWord)) res = min(res, count);
for (auto &dstWord: wordList) {
if (!us.count(dstWord) && transform(curWord, dstWord)) {
us.insert(dstWord);
nextWords.push_back(dstWord);
}
}
}
words = nextWords;
nextWords.clear();
}
return res == INT_MAX ? 0 : res;
}
};
*/
基于LeetCode的C++编程练习与解题设计源码分享 （584个子文件） 
0151.c 969B 0127.cpp 7KB util.cpp 5KB 0912.cpp 4KB 0207.cpp 4KB 1494.cpp 4KB 1568.cpp 4KB 0043.cpp 4KB 0679.cpp 3KB 0336.cpp 3KB 0004.cpp 3KB 0794.cpp 3KB 1452.cpp 3KB 0146.cpp 3KB 0239.cpp 3KB 0355.cpp 3KB 0297.cpp 3KB 0210.cpp 3KB 0147.cpp 3KB S-expression解析和计算.cpp 3KB 0073.cpp 3KB 0460.cpp 3KB 0227.cpp 3KB 0236.cpp 3KB 0130.cpp 3KB 0994.cpp 2KB 1451.cpp 2KB 0013.cpp 2KB 0125.cpp 2KB 0005.cpp 2KB 1606.cpp 2KB 1116.cpp 2KB 1835.cpp 2KB 0149.cpp 2KB 1477.cpp 2KB 人民币转换.cpp 2KB 0015.cpp 2KB 0148.cpp 2KB 0037.cpp 2KB 0094.cpp 2KB 0215.cpp 2KB 0049.cpp 2KB 0046.cpp 2KB 表示数值的字符串.cpp 2KB 0365.cpp 2KB 1483.cpp 2KB 0212.cpp 2KB 0378.cpp 2KB 0144.cpp 2KB 0140.cpp 2KB 0093.cpp 2KB 0529.cpp 2KB 0034.cpp 2KB 0116.cpp 2KB 0990.cpp 2KB 1627.cpp 2KB 0332.cpp 2KB 0106.cpp 2KB 0054.cpp 2KB 0017.cpp 2KB 0455.cpp 2KB 0189.cpp 2KB 1670.cpp 2KB 0040.cpp 2KB 1028.cpp 2KB 0547.cpp 2KB 1005.cpp 2KB 1669.cpp 2KB 1195.cpp 2KB 0381.cpp 2KB 1071.cpp 2KB 二叉搜索树的第k大节点.cpp 2KB 0133.cpp 2KB 0016.cpp 2KB 0020.cpp 2KB 0289.cpp 2KB 0089.cpp 2KB 0328.cpp 2KB 0105.cpp 2KB 0539.cpp 2KB 0029.cpp 2KB 0295.cpp 2KB 0060.cpp 2KB 1515.cpp 2KB from-start-to-end.cpp 2KB 1584.cpp 2KB 模式匹配.cpp 2KB 0063.cpp 2KB 0120.cpp 2KB 0211.cpp 2KB 0051.cpp 2KB 0845.cpp 2KB 1631.cpp 2KB 0052.cpp 2KB 0999.cpp 2KB 1583.cpp 1KB 恢复空格.cpp 1KB 合法ip.cpp 1KB 1562.cpp 1KB 1450.cpp 1KB共 584 条
- 1
- 2
- 3
- 4
- 5
- 6
资源评论
lly202406
- 粉丝: 4075
最新资源
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
