Dynamic planning - force buckle

Dynamic programming

Edit distance

analysis

1. There are three ways to make dynamic changes in the topic , Insert 、 Delete and modify a character .
   Delete m[i][j] = m[i - 1][j] + 1
   Change m[i][j] = m[i - 1][j - 1] + 1
   increase m[i][j] = m[i ][j - 1] + 1
2. The initial state ： If no one can match, the whole word length is required .
   m[i][0] = i
   m[0][j] = j

Code

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];
    }
}