Amazon : 字符串最短路径

字符串和字符串之间的转变可以通过插入，修改，删除字符来完成。插入，修改或删除了一个字符就是编辑了一步。比如cat->cut->put->pult, cat通过三步转换成了pult. 现在给你一个字典的所有数据， 求出任意两个单词之间的最少转换步骤，其中每一步转换结果也需要是字典中的一个单词。

我发现所有的题我都只会naive的方法，还是得等我们石溪的gooooopan来回答吧

回复 2# needyou

回复 3# darksteel


    我今天被geometry日了

回复 4# needyou
我也还有考试，感觉动力不足。。

回复  needyou
我也还有考试，感觉动力不足。。
darksteel 发表于 2011-5-19 13:06

来，给你打打气

你就是这个样子所以才是个ms，哈哈哈，够歹毒吧

回复 6# needyou
{:4_83:}不太明白，不过我确实得复习明天上午的考试才行了。。

字符串编辑距离本来是典型的DP问题，但要求都是字典里的单词就不太好办。我再想如果要求所有单词两两之间的路径，不妨就把整个字典建成一个无向图，任意两个可以通过一次编辑达到的单词之间存在边，然后就转化为求最短路径了。不过判断两个单词是否能通过编辑一次达到也不是那么直接，不知道有没有线性的方法

首先要建图，建图可以考虑用hash的方法，增加一个字符，比如*,表示任意值。
对于一个单词，比如说abcd，我们分别将*bcd，a*cd,ab*d,abc*（修改字符），*abcd,a*bcd,ab*cd,abc*d,abcd*（插入字符），bcd,acd,abd,abc(删除字符)，插入hash表，如果已经存在了，则说明存在可一步到达的单词，将其连边

至于求最短路，可以使用启发式搜索，因为两个单词的长度为la和lb的话，修改次数<=max(la,lb)，因此实际路径相比于单词量来说是非常非常小的