1. 简述

    使用两个字符串之间的编辑距离计算它们的相似度，相似度=1/(编辑距离+1)。两个字符串的编辑距离：指通过下面三种操作可以将两个字符串变为相同的字符串需要的次数。1) 修改一个字符 2) 增加一个字符 3) 删除一个字符。

    对于"abcdefg"和"abcdef"两个字符串来说，我们认为可以通过增加/减少一个"g"的方式来达到目的，将两个字符串变成相同字符串的最小步数为1，因此编辑距离为1，相似度=1/(1+1)=0.5。

    给定两个字符，编程实现计算它们的相似度。

2. 思路

    这道题我暂时没什么新的想法，基本上是沿用书上的方法。见过一个论文是计算字典树中字符串的相似度的，回来有机会把那个看看。

    假设两个字符串为A和B，当前匹配A[i]与B[j]。

    如果A[i]==B[j]，当前编辑距离+=A[i+1，Len_A-1]与B[j+1，Len_B-1]编辑距离。

    如果A[i]!=B[j]，当前编辑距离+=Min {

{A[i+1，Len_A-1]与B[j+1，Len_B-1]编辑距离} ,

                                                      {A[i，Len_A-1]与B[j+1，Len_B-1]编辑距离},

                                                      {A[i+1，Len_A-1]与B[j，Len_B-1]编辑距离}  }  + 1。   

    采用备忘录方法，使用int Record[len_A][len_B]数组将计算过的编辑距离存储，Record[i][j]，表示A[i,Len_A-1]与B[j,Len_B-1]的编辑距离。

    最后相似度=1.0 / (编辑距离+1)

3. 参考

    编程之美，3.3节，计算字符串的相似度