Edit Distance
给两个字符串和三种操作, 添加/删除/替换其中一个字符. 问怎么最少的操作得到另一个字符串. 这个是经典算法. 用dp做, dp[i][j] 代表在w1的i和w2的j的最少操作.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
public class Solution { public int minDistance(String word1, String word2) { int n = word1.length(); int m = word2.length(); int[][]dp = new int[n+1][m+1]; for(int i = 0 ; i < m+1; i++) dp[0][i] = i; for(int i = 0 ; i < n+1; i++) dp[i][0] = i; for(int i = 1; i < n+1; i++){ for(int j = 1; j < m+1; j++) { if(word1.charAt(i-1) == word2.charAt(j-1)) dp[i][j] = dp[i-1][j-1]; else dp[i][j] = 1 + Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]); } } return dp[n][m]; } } |