题目:给定任意两个字符串,计算它们的相似度.
如果将两个不相同的字符串变得相同，通过修改，增加，删除来实现:
1.修改一个字符（如把“a”替换为“b”）;
2.增加一个字符（如把“abdd”变为“aebdd”)
3.删除一个字符（如把“travelling”变为“traveling”）;
“abcdefg”和“abcdef”两个字符串来说，可以通过增加/减少一个“g”的方式来达到目的,都仅需要操作一 次 。把这个操作所需要的次数定义为两个字符串的距离，而相似度等于“距离+1”的倒数。“abcdefg”和“abcdef”的距离为1，相似度 为1/2=0.5.
递归解法
如果有两个串A=xabcdae和B=xfdfa，它们的第一个字符是 相同的，只要计算A[2,...,7]=abcdae和B[2,...,5]=fdfa的距离就可以了。但是如果两个串的第一个字符不相同，那么可以进行 如下的操作（lenA和lenB分别是A串和B串的长度）。
1.删除A串的第一个字符，然后计算A[2,...,lenA]和B[1,...,lenB]的距离。
2.删除B串的第一个字符，然后计算A[1,...,lenA]和B[2,...,lenB]的距离。
3.修改A串的第一个字符为B串的第一个字符，然后计算A[2,...,lenA]和B[2,...,lenB]的距离。
4.修改B串的第一个字符为A串的第一个字符，然后计算A[2,...,lenA]和B[2,...,lenB]的距离。
5.增加B串的第一个字符到A串的第一个字符之前，然后计算A[1,...,lenA]和B[2,...,lenB]的距离。
6.增加A串的第一个字符到B串的第一个字符之前，然后计算A[2,...,lenA]和B[1,...,lenB]的距离。
在这个题目中，我们并不在乎两个字符串变得相等之后的字符串是怎样的。所以，可以将上面的6个操作合并为：
1.一步操作之后，再将A[2,...,lenA]和B[1,...,lenB]变成相字符串。
2.一步操作之后，再将A[2,...,lenA]和B[2,...,lenB]变成相字符串。
3.一步操作之后，再将A[1,...,lenA]和B[2,...,lenB]变成相字符串。
通过以上1和6,2和5，3和4的结合操作，最后两个字符串每个对应的字符会相同，但是这三种操作产生的最终的两个字符串是不一样的。我们不知道通过上述的三种结合那种使用的操作次数是最少的。所以我们要比较操作次数来求得最小值。
核心实现代码:
<pre><code>` func calculate_distance(strA:String,beginA:Int, endA:Int,strB:String,beginB:Int,endB:Int)->Int {
if beginA > endA {
if beginB > endB {
return 0
} else {
return endB - beginB + 1
}
}
if beginB > endB {
if beginA > endA {
return 0
} else {
return endA - beginA + 1
}
}
let beginStrA:String = strA[beginA]
let beginStrB:String = strB[beginB]
if beginStrA == beginStrB {
return calculate_distance(strA: strA, beginA: beginA + 1, endA: endA, strB: strB, beginB: beginB + 1, endB: endB)
} else {
let d1:Int = calculate_distance(strA: strA, beginA: beginA, endA: endA, strB: strB, beginB: beginB + 1, endB: endB)
let d2:Int = calculate_distance(strA: strA, beginA: beginA + 1, endA: endA, strB: strB, beginB: beginB, endB: endB)
let d3:Int = calculate_distance(strA: strA, beginA: beginA + 1, endA: endA, strB: strB, beginB: beginB + 1, endB: endB)
return min(a: d1, b: d2, c: d3) + 1
}
}`</code></pre>
动态规划
递归解法中有部分计算属于重复计算，可以通过动态规范表的形式，将上次计算的结果存储起来:
<pre><code>` func calculate_distance2(strA:String,strB:String)->Int {
let lenA:Int = strA.characters.count
let lenB:Int = strB.characters.count
let data:[Int] = [Int].init(repeating: 0, count: lenB + 1)
var temp:[[Int]] = [[Int]].init(repeating: data, count: lenA + 1)
for i in 1...lenA {
temp[i][0] = i
}
for j in 1...lenB {
temp[0][j] = j
}
for i in 1...lenA {
for j in 1...lenB {
let tempA:String = strA[i - 1]
let tempB:String = strB[j - 1]
if(tempA == tempB) {
temp[i][j] = temp[i - 1][j - 1];
} else {
temp[i][j] = min(a: temp[i - 1][j], b: temp[i][j - 1], c: temp[i - 1][j - 1]) + 1
}
}
}
return temp[lenA][lenB]
}
private func min(a:Int,b:Int,c:Int) -> Int {
let temp:Int = a > b ? b : a;
let result:Int = temp > c ? c : temp;
return result
}`</code></pre>
测试代码:
<pre>code>`var similarity:Similarity = Similarity()
var strA:String = "abcdef"
var strB:String = "abcdf"
var distance:Int = similarity.calculate_distance(strA: strA, beginA: 0, endA: strA.characters.count - 1, strB: strB, beginB: 0, endB: strB.characters.count - 1)
var distance2:Int = similarity.calculate_distance2(strA: strA, strB: strB)
var similar:Double = 1.0 / (Double)(distance + 1)
print("FlyElephant--(strA)和(strB)的距离:(distance)-相似度:-(similar)-距离:(distance2)")`</code></pre>
