題目:給定任意兩個(gè)字符串,計(jì)算它們的相似度.
如果將兩個(gè)不相同的字符串變得相同趟径，通過修改裁着，增加英古，刪除來實(shí)現(xiàn):
1.修改一個(gè)字符（如把“a”替換為“b”）;
2.增加一個(gè)字符（如把“abdd”變?yōu)椤癮ebdd”)
3.刪除一個(gè)字符（如把“travelling”變?yōu)椤皌raveling”）;
“abcdefg”和“abcdef”兩個(gè)字符串來說帅戒，可以通過增加/減少一個(gè)“g”的方式來達(dá)到目的,都僅需要操作一 次 玛歌。把這個(gè)操作所需要的次數(shù)定義為兩個(gè)字符串的距離，而相似度等于“距離+1”的倒數(shù)擎椰≈ё樱“abcdefg”和“abcdef”的距離為1，相似度 為1/2=0.5.
遞歸解法
如果有兩個(gè)串A=xabcdae和B=xfdfa达舒，它們的第一個(gè)字符是 相同的值朋，只要計(jì)算A[2,...,7]=abcdae和B[2,...,5]=fdfa的距離就可以了。但是如果兩個(gè)串的第一個(gè)字符不相同巩搏，那么可以進(jìn)行 如下的操作（lenA和lenB分別是A串和B串的長(zhǎng)度）昨登。
1.刪除A串的第一個(gè)字符，然后計(jì)算A[2,...,lenA]和B[1,...,lenB]的距離贯底。
2.刪除B串的第一個(gè)字符丰辣，然后計(jì)算A[1,...,lenA]和B[2,...,lenB]的距離。
3.修改A串的第一個(gè)字符為B串的第一個(gè)字符禽捆，然后計(jì)算A[2,...,lenA]和B[2,...,lenB]的距離笙什。
4.修改B串的第一個(gè)字符為A串的第一個(gè)字符，然后計(jì)算A[2,...,lenA]和B[2,...,lenB]的距離胚想。
5.增加B串的第一個(gè)字符到A串的第一個(gè)字符之前琐凭，然后計(jì)算A[1,...,lenA]和B[2,...,lenB]的距離。
6.增加A串的第一個(gè)字符到B串的第一個(gè)字符之前浊服，然后計(jì)算A[2,...,lenA]和B[1,...,lenB]的距離统屈。
在這個(gè)題目中胚吁，我們并不在乎兩個(gè)字符串變得相等之后的字符串是怎樣的。所以愁憔，可以將上面的6個(gè)操作合并為：
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的結(jié)合操作，最后兩個(gè)字符串每個(gè)對(duì)應(yīng)的字符會(huì)相同激蹲，但是這三種操作產(chǎn)生的最終的兩個(gè)字符串是不一樣的棉磨。我們不知道通過上述的三種結(jié)合那種使用的操作次數(shù)是最少的。所以我們要比較操作次數(shù)來求得最小值学辱。
核心實(shí)現(xiàn)代碼:
<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>
動(dòng)態(tài)規(guī)劃
遞歸解法中有部分計(jì)算屬于重復(fù)計(jì)算乘瓤，可以通過動(dòng)態(tài)規(guī)范表的形式，將上次計(jì)算的結(jié)果存儲(chǔ)起來:
<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>
測(cè)試代碼:
<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>
