Edit Distance
给两个字符串和三种操作, 添加/删除/替换其中一个字符. 问怎么最少的操作得到另一个字符串. 这个是经典算法. 用dp做, dp[i][j] 代表在w1的i和w2的j的最少操作.
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];
}
}