Amazon : 字符串最短路径

回复 10# epic
这个建图代价太大了吧，每个单词所有一步能达到的单词很多，要全枚举出来状态太多，而且带着星号能匹配的两个单词不能保证hash过后还一样。而且两个单词之间的路径长度还是可能达到la+lb-1的。
我觉得还是就n^2枚举单词对，然后判断两个单词是否能一步达到，这个好像是可以线性出来的：
若长度差1以上，不可能
若长度相等，判断不相同的字符个数是否为1
若长度差1，则从头开始匹配，允许一次失配，让长的单词略过该字符，如果再次失配就不可能。
这样就能建起图来，不过n比较大的情况下，时间和空间都不太能接受。要求所有的最短距离的话，最直接的就是floyd算法，但复杂度是n^3。。如果只是求给定的两个单词的最短距离，倒是可以用dijkstra或者双向的BFS。

回复 11# darksteel

用hash的方法建图，时间复杂度是O(n*l)l是单词长度，这比O(n^2)小了不知道多少了

而且枚举单词对的复杂度严格上说是O(n^2*l)，用hash整整小了一个数量级

当然我这都是没有考虑把边连出来的复杂度，如果本来就是个完全图，那的确怎么着都要o(n^2)，但很明显这是个稀疏图

回复 12# epic
还是没搞懂怎么hash建图。。你上面说的abcd，要插入什么进去呢？最后得到的结果是什么呢？

回复 13# darksteel

换个说法，就是对模式进行hash。

比如说abcd，那么abcd一步可达的模式就是*abcd a*bcd  ab*cd  abc*d  abcd*，*bcd，a*cd,ab*d,abc*，bcd，acd，abd，abc这么几种

把每种模式做个hash值插入

考虑一个单词能由哪些可达的时候，就考虑它符合哪些模式

比如说ebcd，这时候，如果有单词通过插入达到它，那么*bcd、e*cd、eb*d、ebc*这四种模式必然出现过（因此查这几个hash值是否存在就可以了）
如果有单词通过删除达到他，那么这个单词必然以前插入过ebcd（因此只要查ebcd是否存在）
如果有单词通过修改达到他，那么也是查*bcd、e*cd、eb*d、ebc*是否存在过。

完了再把这个单词能构成的模式插进去。对ebcd来说，就是*ebcd,e*bcd,eb*cd,ebc*d,ebcd*，bcd,ecd,ebd,ebc,*bcd,e*cd,eb*d,ebcd*。

这里*是一个我自己定义的特殊字符，用@啊#啊也可以。


因为每个单词所构成的模式必然是O(l)的，因此对于每个单词我们只需要计算O(l)次hash值

回复 14# epic
我明白你的意思了。直观上想觉得空间消耗有点大，但当n比较大的时候，O(n)以上的做法都是不可接受的，这应该算是个很可行的做法

我觉得是DP，复杂度O(len(S1)*len(S2)), A[i][j]= min{ A[i-1][j-1]+0/1 或者 A[i-1][j] 或者 A[i][j-1] }

回复 16# bill
字符串编辑距离本来是典型的DP问题，但要求路径上都是字典里的单词就不太好DP了