前言
最近翻開之前一本工作筆記夸赫，回想起之前做一個搜索功能，其中有用到計算相似度時用過編輯距離算法。記得也是leetcode hard難度诉瓦，本文權(quán)當個回顧吧。
簡介
Levenshtein距離力细，用于計算兩個字符串之間的編輯距離睬澡。編輯距離的一種。是指兩個字符串之間眠蚂，由一個轉(zhuǎn)換成另一個所需的最少編輯操作次數(shù)煞聪。算法概念是俄羅斯科學家弗拉基米爾·萊文斯坦（Levenshtein · Vladimir I）于1965年提出。允許的編輯操作包括：替換逝慧、插入昔脯、刪除啄糙。
算法實現(xiàn)
1. 設(shè)定dp數(shù)組意義
dp[i][j]代表的意思為：以i - 1為結(jié)尾的字符串w1和以j - 1為結(jié)尾的字符串w2，最近的編輯距離記為dp[i][j]云稚。
2. 推導過程
比較w1在i - 1位置和w2在j - 1位置的字符隧饼，分為兩種情況。
1. 不等
插入
例如w1 = "ab", w2 = "bca"静陈。
??若在w1上加字符：為了使使w[i - 1]與w2[j - 1]字符相等燕雁，那么就需要在w1的i - 1位置插入一個"b"，w1的長度增加1鲸拥。也就是說此時以i-2為結(jié)尾的w1和以j-1位結(jié)尾的w2的最近編輯距離增加了一個插入操作贵白。
即 dp[i][j]= dp[i - 1][j] + 1;
??若在w2上加字符：使w[i - 1]與w2[j - 1]相同，那么就需要在w2的j - 1位置插入一個"a"崩泡，w2的長度增加1禁荒。也就是說此時以i - i為結(jié)尾的w1和以j - 2位結(jié)尾的w1的最近編輯距離增加了一個插入操作。
即 dp[i][j]= dp[i][j - 1] + 1;替換
w1替換w1[i - 1]角撞，使其與word2[j - 1]相同呛伴，那么以下標i - 2為結(jié)尾的w1與i - 2為結(jié)尾的w2的最近編輯距離加一個替換字符的操作。
即 dp[i][j] = dp[i - 1][j - 1] + 1;刪除
刪除與插入其實所需要的操作數(shù)是一樣的谒所。在w1上刪除一個字符热康，等同于在w2上插入一個字符的操作數(shù)。
以上三種操作劣领，取最少編輯距離即：dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
2. 相等
若w1[i - 1] == w2[j - 1]姐军，無需編輯。
即 dp[i][j] = dp[i - 1][j - 1];
通過以上兩種情況尖淘，可推導出動態(tài)轉(zhuǎn)移方程：
邊界情況:
一個空串和一個非空串的編輯距離為dp[i][0] = i和dp[0][j] = j奕锌，dp[i][0]相當于對w1執(zhí)行i次刪除操作，dp[0][j]相當于對w1執(zhí)行j次操作村生。
class Solution {
public:
int minDistance(string word1, string word2) {
int size1 = word1.size(), size2 = word2.size();
vector<vector<int>> dp(size1 + 1, vector<int>(size2 + 1, 0));
for (int i = 0; i <= size1; i++) {
dp[i][0] = i;
}
for (int i = 0; i <= size2; i++) {
dp[0][i] = i;
}
for (int i = 1; i <= size1; i++) {
for (int j = 1; j <= size2; j++) {
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
}else {
dp[i][j] = min({dp[i][j - 1], dp[i - 1][j - 1], dp[i - 1][j]}) + 1;
}
}
}
return dp[size1][size2];
}
};
其他
- 用戶的一些輸入模糊匹配惊暴。如Elasticsearch的Fuzzy query。
- 如果某場景要求string的前部分越相似分數(shù)越高趁桃。例如對于計算"12A45"辽话，"12345A"和"12345"的Levenshtein距離值是相同的。此時可用Jaro–Winkler distance卫病。Jaro-Winkler distance會給起始部分就相同的字符串更高的分數(shù)油啤。有興趣的小伙伴可以去google下具體實現(xiàn)。
