文件名称:求字符串编辑距离 动态规划 java
文件大小:1KB
文件格式:JAVA
更新时间:2011-12-28 16:13:58
求字符串编辑距离
试验题目:近似字符串匹配问题计算两个字符串s1+ch1, s2+ch2的编辑距离有这样的性质: 1. d(s1,””) = d(“”,s1) = |s1| d(“ch1”,”ch2”) = ch1 == ch2 ? 0 : 1; 2. d(s1+ch1,s2+ch2) = min( d(s1,s2)+ ch1==ch2 ? 0 : 1 , d(s1+ch1,s2)+1, d(s1,s2+ch2)+1 );