June 19, 2015
Problem statement:
Word Ladder I
Given two words (start and end),
and a dictionary, find the length of shortest transformation sequence
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 = "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.
读了上面二个网页, 明白如何分析这个问题. 知道是图的问题, 而且是个难题. 觉得很不错, 刷题可以长见识. 知道自己还不会轻松地分析, 或者说, 想明白思路. 先写写代码, 调试几次, 帮助自己理解.
先看第一篇分析:
思路：
LeetCode中为数不多的考图的难题。尽管题目看上去像字符串匹配题，但从“shortest transformation sequence from start to end”还是能透露出一点图论中最短路径题的味道。如何转化？
1. 将每个单词看成图的一个节点。
2. 当单词s1改变一个字符可以变成存在于字典的单词s2时，则s1与s2之间有连接。
3. 给定s1和s2，问题I转化成了求在图中从s1->s2的最短路径长度。而问题II转化为了求所有s1->s2的最短路径。
无论是求最短路径长度还是求所有最短路径，都是用BFS。在BFS中有三个关键步骤需要实现:
1. 如何找到与当前节点相邻的所有节点。
这里可以有两个策略：
(1) 遍历整个字典，将其中每个单词与当前单词比较，判断是否只差一个字符。复杂度为：n*w，n为字典中的单词数量，w为单词长度。
(2) 遍历当前单词的每个字符x，将其改变成a~z中除x外的任意一个，形成一个新的单词，在字典中判断是否存在。复杂度为：26*w，w为单词长度。
这里可以和面试官讨论两种策略的取舍。对于通常的英语单词来说，长度大多小于100，而字典中的单词数则往往是成千上万，所以策略2相对较优。
2. 如何标记一个节点已经被访问过，以避免重复访问。
可以将访问过的单词从字典中删除。
3. 一旦BFS找到目标单词，如何backtracking找回路径？
再看第二篇分析:
/**
* Solution: Graph BFS
* 这道题想明白后非常简单，其实就是求最短路径问题，自然是BFS方法，其实问题可以用Graph来很好的解释。
* 顶点是每个字符串，如果相差一个字符，我们就可以连一条边，
* 一个字符串的边的数量最大值可能是 25 * L. 然后连线，形成Graph, 这样就是start - end的最短路径问题.
* 每次我们可以从start 出发，找adjacent string, 然后 enqueue, 下次再遍历下一层，这样第一次到end的时候，shortest = length + 1.
*
* 这题目的特点:
* 1. dict来代替BFS 中 visited 标记，直接remove from dict 就代表遍历过了 或者 不存在
* 2. 都小写字母, 字符串长度固定. 问题简单化(如果不固定，就不是只换一个char这种简单情形了，会复杂的多，跟这题也会大不相同)
*
* Time Complexity. 有点不太确定
* 最差情况: 对于每一个词, 查询应该是26*wordLength. 然后一直遍历完所有dict才找到答案. O(dict.size * 26*wordLength)
* Space 只需要一个Queue 存储邻接点，最大是dict的size, 因为dict不会是规模的，所以算是O(1)
*/
大概知道了解决方案，练习写代码．
No comments:
Post a Comment