## Thursday, November 27, 2014

### [LeetCode] Word Ladder I, II

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence 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"]`
As one shortest transformation is `"hit" -> "hot" -> "dot" -> "dog" -> "cog"`,
return its length `5`.
Note:
• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

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.

LeetCode中为数不多的考图的难题。尽管题目看上去像字符串匹配题，但从“shortest transformation sequence from start to end”还是能透露出一点图论中最短路径题的味道。如何转化？

1. 将每个单词看成图的一个节点。
2. 当单词s1改变一个字符可以变成存在于字典的单词s2时，则s1与s2之间有连接。
3. 给定s1和s2，问题I转化成了求在图中从s1->s2的最短路径长度。而问题II转化为了求所有s1->s2的最短路径。

1. 如何找到与当前节点相邻的所有节点。

(1) 遍历整个字典，将其中每个单词与当前单词比较，判断是否只差一个字符。复杂度为：n*w，n为字典中的单词数量，w为单词长度。
(2) 遍历当前单词的每个字符x，将其改变成a~z中除x外的任意一个，形成一个新的单词，在字典中判断是否存在。复杂度为：26*w，w为单词长度。

2. 如何标记一个节点已经被访问过，以避免重复访问。

3. 一旦BFS找到目标单词，如何backtracking找回路径？

 ``` 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``` ```class Solution { public: int ladderLength(string start, string end, unordered_set &dict) { dict.insert(end); queue> q; q.push(make_pair(start,1)); while(!q.empty()) { string s = q.front().first; int len = q.front().second; if(s==end) return len; q.pop(); vector neighbors = findNeighbors(s, dict); for(int i=0; i findNeighbors(string s, unordered_set &dict) { vector ret; for(int i=0; i