要求
给定两个字符串，一个为起始字符串，一个为终点字符串，以及一个字典，求起始字符串转化为终点字符串的最短路径,返回转化路径的长度。
具体要求：
1、一次只能变换一个单词；
2、转化过程出现的单词必须是字典里的。
例子：
beginWord = “hit”
endWord = “cog”
dictionary = [“hot”,“dot”,“dog”,“lot”,“log”]
transformation："hit"->“hot”->“dot”->“dog”->“cog”
return its length 5
做法
既然要求最短，我们可以借助图BFS的思想来解决这个问题，这个问题可以转化为图的源最短路径问题，虽然解题过程中没有用到图，但用到图的思想。
从源字符串出发，先遍历完当前字符串可能变化的情况，如果还没变成终点字符串，则继续下一层遍历，直到可以变成终点字符串，返回转化步数。如果所有情况都遍历完了还不能变成终点字符串，则返回0。
代码实现
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
| #include <iostream>
#include <queue>
#include <unordered_set>
#include <unordered_map>
using namespace std;
/**
* 记录源字符串转化当前字符串的路径
* word 当前字符串
* pre 前驱字符串
* isVisited 当前字符串是否被访问
* size 源字符串转化为当前字符串的过程经过的字符串的个数，即转化步数
**/
struct Node {
string word;
string pre;
bool isVisited;
int size;
Node(string word)
:word(word),isVisited(false),size(0){
}
};
class Solution {
public:
int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
unordered_map<string, Node*> word_map;
for (auto pos = wordList.begin(); pos!=wordList.end(); pos++) {
Node* node = new Node(*pos);
word_map[*pos] = node;
}
Node* begin = new Node(beginWord);
begin->isVisited = true;
begin->size = 1;
word_map[beginWord] = begin;
Node* end = new Node(endWord);
word_map[endWord] = end;
queue<Node*> queue;
queue.push(word_map[beginWord]);
while (!queue.empty()) {
Node* current_node = queue.front();
queue.pop();
//遍历字符串每一个位置
for (int i = 0; i<current_node->word.length(); i++) {
for (char j = 'a'; j<='z'; j++) {
string word = current_node->word;
//替换字符，word变成一个新字符串
word[i] = j;
if (word==endWord) {
word_map[word]->size = current_node->size+1;
return word_map[word]->size;
}
else if (word_map.count(word)==1&&word_map[word]->isVisited==false) {
word_map[word]->isVisited = true;
word_map[word]->pre = current_node->word;
word_map[word]->size = current_node->size+1;
queue.push(word_map[word]);
}
}
}
}
return 0;
}
};
int main(int argc, const char * argv[]) {
unordered_set<string> wordList = {"hot","dot","dog","lot","log"};
Solution s;
cout<<s.ladderLength("hit", "cog", wordList)<<endl;
return 0;
}
|