Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:
- Only one letter can be changed at a time
- Each intermediate word must exist in the dictionary
For example,
Given:
start =
end =
dict =
start =
"hit"
end =
"cog"
dict =
["hot","dot","dog","lot","log"]
Return
[ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ]
Note:
- All words have the same length.
- All words contain only lowercase alphabetic characters.
[Thoughts]
解法一,递归
1. 首先生成不同字符串之间的跳转函数(Func[A][B] means how many char need changed if A transfer to B),比如{"a", "b", "c"}
a b c
a 0 1 1
b 1 0 1
c 1 1 0
2. 有了转移方程之后,直接递归就好了。
在实现中,由于unordered_set不支持[]操作,所以我额外拷贝到vector里面来做(没有使用hash),浪费了多余的时间。可以过小数据,但是过不了大数据。
1: int DiffDict[1000][1000];
2: int visited[1000];
3: void findtran(string& start, string& end, vector<string> &dict, int curIndex,
4: int step, int& min, vector<vector<string>>& result, vector<string>& candidate)
5: {
6: if(start == end)
7: {
8: if(step < min)
9: {
10: min = step;
11: result.clear();
12: result.push_back(candidate);
13: }
14: else if(step == min)
15: {
16: result.push_back(candidate);
17: }
18: return;
19: }
20: for(int i =1; i< dict.size(); i++)
21: {
22: if(visited[i] ==1 || DiffDict[curIndex][i] !=1)
23: continue;
24: visited[i] =1;
25: candidate.push_back(dict[i]);
26: findtran(dict[i], end, dict, i, step+1, min, result, candidate);
27: candidate.pop_back();
28: visited[i] =0;
29: }
30: }
31: vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
32: vector<vector<string>> result;
33: assert(dict.size() < 1000);
34: vector<string> dictV;
35: //copy data to vector since unordered_set not support []
36: for(unordered_set<string>::iterator it = dict.begin(); it!=dict.end(); ++it)
37: {
38: dictV.push_back(*it);
39: }
40: //add start as head
41: vector<string>::iterator it = std::find(dictV.begin(), dictV.end(),start);
42: if(it!= dictV.end())
43: {
44: dictV.erase(it);
45: }
46: dictV.insert(dictV.begin(),start);
47: visited[0] =1;
48: //add end as tail
49: it = std::find(dictV.begin(), dictV.end(),end);
50: if(it!= dictV.end())
51: {
52: dictV.erase(it);
53: }
54: dictV.push_back(end);
55: //preprocess trans metrics
56: for(int i=0; i<dictV.size(); i++)
57: {
58: for(int j=i; j<dictV.size(); j++)
59: {
60: int diff=0;
61: for(int k=0; k< it->size(); k++)
62: {
63: if(dictV[i][k] != dictV[j][k]) diff++;
64: }
65: DiffDict[i][j] = diff;
66: DiffDict[j][i] = diff;
67: }
68: }
69: int step =0;
70: int min = INT_MAX;
71: vector<string> candidate;
72: candidate.push_back(start);
73: findtran(start, end, dictV, 0,step, min, result, candidate);
74: return result;
75: }
考虑到题目已经提示了应该使用unordered_set来做,应该有基于hash的解法。
No comments:
Post a Comment