近似暴力的BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
int sz = wordList.size();
vector<int> visited(sz, 0);
int wordLength = wordList[0].size();
vector<string> candidates{ beginWord };
int ret = 1;
while(!candidates.empty())
{
++ret;
vector<string> tmp;
for(auto& cand : candidates)
{
for(int j = 0; j < sz; ++j)
{
if(visited[j])
continue;
auto word = wordList[j];
int diff = 0;
for(int i = 0; i < wordLength; ++i)
{
if(word[i] != cand[i])
++diff;
}
if(diff == 1)
{
tmp.push_back(word);
if(word == endWord)
return ret;
visited[j] = 1;
}
}
}
candidates = tmp;
}
return 0;
}
};
|
BFS+虚拟节点
1631071640321.jpg
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
int ret = 0;
for(auto& word : wordList)
addEdge(word);
addEdge(beginWord);
if(!map.count(endWord))
return 0;
queue<int> q;
int endId = map[endWord];
q.push(map[beginWord]);
int step = 1;
vector<int> visited(nodeNum, 0);
while(!q.empty())
{
++step;
for(int i = 0, sz = q.size(); i < sz; ++i)
{
auto p = q.front();
q.pop();
if(visited[p])
continue;
visited[p] = 1;
for(auto neighbor : graph[p])
{
if(neighbor == endId)
return step / 2 + 1;
q.push(neighbor);
}
}
}
return 0;
}
private:
int nodeNum = 0;
vector<vector<int>> graph;
unordered_map<string, int> map;
void addWord(string& s)
{
if(!map.count(s))
{
map.insert({s, nodeNum++});
graph.emplace_back();
}
}
void addEdge(string& s)
{
addWord(s);
int id1 = map[s];
for(auto& ch : s)
{
auto tmp = ch;
ch = '*';
addWord(s);
int id2 = map[s];
graph[id1].push_back(id2);
graph[id2].push_back(id1);
ch = tmp;
}
}
};
|
写法二
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
int ret = 0;
for(auto& word : wordList)
addEdge(word);
addEdge(beginWord);
if(!map.count(endWord))
return 0;
queue<int> q;
int endId = map[endWord];
q.push(map[beginWord]);
vector<int> dis(nodeNum, INT_MAX);
dis[map[beginWord]] = 0;
while(!q.empty())
{
auto p = q.front();
q.pop();
if(neighbor == endId)
return dis[neighbor] / 2 + 1;
for(auto neighbor : graph[p])
{
if(dis[neighbor] == INT_MAX)
{
dis[neighbor] = dis[p] + 1;
q.push(neighbor);
}
}
}
return 0;
}
private:
int nodeNum = 0;
vector<vector<int>> graph;
unordered_map<string, int> map;
void addWord(string& s)
{
if(!map.count(s))
{
map.insert({s, nodeNum++});
graph.emplace_back();
}
}
void addEdge(string& s)
{
addWord(s);
int id1 = map[s];
for(auto& ch : s)
{
auto tmp = ch;
ch = '*';
addWord(s);
int id2 = map[s];
graph[id1].push_back(id2);
graph[id2].push_back(id1);
ch = tmp;
}
}
};
|
BFS双向搜索
从begin和end同时开始，如果他们相遇了就是结果，这样可以减少许多分叉的占用
1631086368533.png
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
| class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
int ret = 0;
for(auto& word : wordList)
addEdge(word);
addEdge(beginWord);
if(!map.count(endWord))
return 0;
queue<int> qBegin;
queue<int> qEnd;
int endId = map[endWord];
int beginId = map[beginWord];
qBegin.push(beginId);
qEnd.push(endId);
vector<int> disBegin(nodeNum, INT_MAX);
vector<int> disEnd(nodeNum, INT_MAX);
disBegin[beginId] = 0;
disEnd[endId] = 0;
while(!qBegin.empty() && !qEnd.empty())
{
for(int i = 0, sz = qBegin.size(); i < sz; ++i)
{
auto p = qBegin.front();
qBegin.pop();
if(disEnd[p] != INT_MAX)
return (disEnd[p] + disBegin[p]) / 2 + 1;
for(auto num : graph[p])
{
if(disBegin[num] == INT_MAX)
{
disBegin[num] = disBegin[p] + 1;
qBegin.push(num);
}
}
}
for(int i = 0, sz = qEnd.size(); i < sz; ++i)
{
auto p = qEnd.front();
qEnd.pop();
if(disBegin[p] != INT_MAX)
return (disEnd[p] + disBegin[p]) / 2 + 1;
for(auto num : graph[p])
{
if(disEnd[num] == INT_MAX)
{
disEnd[num] = disEnd[p] + 1;
qEnd.push(num);
}
}
}
}
return 0;
}
private:
int nodeNum = 0;
vector<vector<int>> graph;
unordered_map<string, int> map;
void addWord(string& s)
{
if(!map.count(s))
{
map.insert({s, nodeNum++});
graph.emplace_back();
}
}
void addEdge(string& s)
{
addWord(s);
int id1 = map[s];
for(auto& ch : s)
{
auto tmp = ch;
ch = '*';
addWord(s);
int id2 = map[s];
graph[id1].push_back(id2);
graph[id2].push_back(id1);
ch = tmp;
}
}
};
|