## Friday, February 22, 2013

### [LeetCode] Word Ladder II, Solution

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:
1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary
For example,
Given:
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.
» Solve this problem

[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. 有了转移方程之后，直接递归就好了。

``````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:       }
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;
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:  }
``````