Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

字符串编辑距离的代码有问题? #392

Open
tinyyard opened this issue Oct 31, 2014 · 0 comments
Open

字符串编辑距离的代码有问题? #392

tinyyard opened this issue Oct 31, 2014 · 0 comments

Comments

@tinyyard
Copy link

1、计算边界条件的时候计数器应该从0开始吧,这样才能给dp[0][0]赋值,否则在最后计算编辑距离的循环中,如果pSource[0] == pTarget[0], 则dp[1][1] = dp[0][0],此时dp[0][0]值未知。虽然我用的java重写的版本中,编译器自动给数组中未赋值的元素置0了,但是,整形数组初始值是根据编译环境不同有差异的吧。
2、在计算编辑距离的嵌套循环中,如果pSource[i - 1] != pTarget[j - 1],也就是在else{}中,dp[i][j]应该等于dp[i - 1][j]、dp[i][j - 1]、dp[i - 1][j-1]三者中的最小值 +1,java中实现是dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1; 因为此时是删除、增加、替换操作三者选一,代码中dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1]);应该指的是编辑距离中只有删除和增加两种操作的情况。

这个是我用java重新实现了算法之后的结论撒如果有什么地方想得不对请多多指教

@tinyyard tinyyard changed the title 字符串编辑距离的算法有问题? 字符串编辑距离的代码有问题? Oct 31, 2014
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant