动态规划 - 编辑距离

class Solution {    public int minDistance(String word1, String word2) {				if (isNull(word1) && isNull(word2)) {            return 0;        }        if (isNull(word1)) {            return word2.length();        }        if (isNull(word2)) {            return word1.length();        }        int l1 = word1.length();        int l2 = word2.length();        int[][] arr = new int[l1 + 1][l2 + 1];        // 初始化        for (int i = 0; i < l1 + 1; ++i) {            arr[i][0] = i;        }        // 初始化        for (int i = 0; i < l2 + 1; ++i) {            arr[0][i] = i;        }        // 通过状态转移方程寻找最优解        for (int i = 1; i < l1 + 1; ++i) {            for (int j = 1; j < l2 + 1; ++j) {                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {                    // 相同                    arr[i][j] = Math.min(Math.min(arr[i - 1][j] + 1, arr[i][j - 1] + 1), arr[i - 1][j - 1]);                } else {                    arr[i][j] = Math.min(Math.min(arr[i - 1][j] + 1, arr[i][j - 1] + 1), arr[i - 1][j - 1] + 1);                }            }        }        return arr[l1][l2];    }    private  boolean isNull(String str) {        return "".equals(str) || null == str;    }}