动态规划-力扣

动态规划

编辑距离

解析

1. 题目中能过进行动态变化的有三种方式，插入、删除与修改一个字符。
   删 m[i][j] = m[i - 1][j] + 1
   改 m[i][j] = m[i - 1][j - 1] + 1
   增 m[i][j] = m[i ][j - 1] + 1
2. 初始状态：如果没有任意一个能过匹配则需要整个单词长度次数。
   m[i][0] = i
   m[0][j] = j

代码

class Solution {
    
    public int minDistance(String word1, String word2) {
    
        /* a[i - 1] -> b[j - 1] k => a[i] -> b[j] k + 1 a[i - 1] -> b[j] k => a[i] -> b[j] k + 1 a[i] -> b[j - 1] k => a[i] -> b[j] k + 1 m[i][0] = i m[0][j] = j */
        char[] w1 = word1.toCharArray();
        char[] w2 = word2.toCharArray();
        final int l1 = w1.length;
        final int l2 = w2.length;
        int[][] m = new int[l1 + 1][l2 + 1];
        for (int i = 0; i <= l1; i++) {
    
            m[i][0] = i;
        }
        for (int i = 0; i <= l2; i++) {
    
            m[0][i] = i;
        }
        for (int i = 1; i <= l1; i++) {
    
            for (int j = 1; j <= l2; j++) {
    
                if (w1[i - 1] == w2[j - 1]) {
    
                    m[i][j] = m[i - 1][j - 1];
                } else {
    
                    m[i][j] = 1 + Math.min(m[i -1][j - 1], Math.min(m[i - 1][j], m[i][j - 1]));
                }
            }
        }
        return m[l1][l2];
    }
}