【Edit Distance】生成的数组是(m+1)*(n+1)和m*n真的有差别吗？

和很多答案比了比，后半部分没有差别。
好吧我觉得错误并不在于生成的二维数组是m*n还是(m+1)*(n+1)，而是在初始化的阶段。
我的逻辑是在二维数组的第一行和第一列中用字符串1的第一个字符和字符串2比，遇到相等的字符就不变，如果不同就把前面的数+1。
答案是构造二维数组(m+1)*(n+1)，用空字符去比字符串1和2.
差别在哪？为什么我的答案就会出错呢？求拍醒。

你这个逻辑不对，随便举个例子吧，比如：word1 = 'aaaaaaaa', word2 = 'aba'.
现在拿word2中的字符分别和word1的第一个字符‘a'比：

1. a == a  => start = 0; 正确
2. a != b => start = 1; 正确
3. a == a => start = 1; 错误！'a' 和 'aba'的distance应为2.

正确的逻辑是：“start不增加的循环最多出现一次”，即第二次出现a == a时就应该跳过。所以你还不如就用m+1,n+1的代码好了。

stellari 发表于 2015-8-11 11:01
你这个逻辑不对，随便举个例子吧，比如：word1 = 'aaaaaaaa', word2 = 'aba'.
现在拿word2中的字符分别和w ...

好的。谢谢！

多加1个往往是为了让代码更好写，原理肯定是一样的。