編輯距離（Edit Distance）瑞筐，也稱(chēng)為L(zhǎng)evenshtein距離鞍盗，是用來(lái)比較兩個(gè)字符串之間的相似度的方法金赦。它可以通過(guò)一系列的編輯操作將一個(gè)字符串轉(zhuǎn)換為另一個(gè)字符串拭宁，包括插入洛退、刪除和替換等操作。
以下是一個(gè)Java代碼示例红淡，用于計(jì)算兩個(gè)字符串之間的編輯距離：
public class EditDistance {
? ? public static int editDistance(String word1, String word2) {
? ? ? ? int m = word1.length();
? ? ? ? int n = word2.length();
? ? ? ? // 初始化距離矩陣
? ? ? ? int[][] dp = new int[m + 1][n + 1];
? ? ? ? for (int i = 0; i <= m; i++) {
? ? ? ? ? ? dp[i][0] = i;
? ? ? ? }
? ? ? ? for (int j = 0; j <= n; j++) {
? ? ? ? ? ? dp[0][j] = j;
? ? ? ? }
? ? ? ? // 計(jì)算距離矩陣
? ? ? ? for (int i = 1; i <= m; i++) {
? ? ? ? ? ? for (int j = 1; j <= n; j++) {
? ? ? ? ? ? ? ? int cost = (word1.charAt(i - 1) == word2.charAt(j - 1)) ? 0 : 1;
? ? ? ? ? ? ? ? dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + cost);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return dp[m][n];
? ? }
? ? public static void main(String[] args) {
? ? ? ? String word1 = "kitten";
? ? ? ? String word2 = "sitting";
? ? ? ? System.out.println("編輯距離為：" + editDistance(word1, word2));
? ? }
}
這個(gè)示例代碼中的 editDistance() 方法接收兩個(gè)字符串作為參數(shù)不狮，計(jì)算并返回它們之間的編輯距離降铸。該方法使用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)在旱，時(shí)間復(fù)雜度為 O(mn)，其中 m 和 n 分別是兩個(gè)字符串的長(zhǎng)度推掸。在這個(gè)示例中桶蝎，我們計(jì)算了單詞"kitten"和"sitting"之間的編輯距離。
