编辑距离算法java
时间: 2023-10-26 18:22:41 浏览: 51
编辑距离算法(Levenshtein Distance)是一种用于计算两个字符串之间的差异程度的算法。它通过插入、删除和替换操作来计算两个字符串之间的最小编辑距离。以下是一个基于Java的编辑距离算法的示例代码:
```java
public class EditDistance {
public static int calculateDistance(String word1, String word2) {
int[][] dp = new int[word1.length() + 1][word2.length() + 1];
for (int i = 0; i <= word1.length(); i++) {
dp[i][0] = i;
}
for (int j = 0; j <= word2.length(); j++) {
dp[0][j] = j;
}
for (int i = 1; i <= word1.length(); i++) {
for (int j = 1; j <= word2.length(); j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
int insert = dp[i][j - 1] + 1;
int delete = dp[i - 1][j] + 1;
int replace = dp[i - 1][j - 1] + 1;
dp[i][j] = Math.min(Math.min(insert, delete), replace);
}
}
}
return dp[word1.length()][word2.length()];
}
public static void main(String[] args) {
String word1 = "kitten";
String word2 = "sitting";
int distance = calculateDistance(word1, word2);
System.out.println("编辑距离: " + distance);
}
}
```
以上代码中,我们使用动态规划(Dynamic Programming)的思想来计算两个字符串之间的最小编辑距离。在主函数中,我们计算了 "kitten" 和 "sitting" 之间的编辑距离,并将结果打印出来。
希望这个示例能帮到你!如有更多问题,请继续提问。