這里LeetCode上兩道題目，難度為中等和困難。

一次編輯

字符串有三種編輯操作:插入一個字符、刪除一個字符或者替換一個字符。 給定兩個字符串，編寫一個函數(shù)判定它們是否只需要一次(或者零次)編輯。

示例 1:

輸入: 
first = "pale"
second = "ple"
輸出: True
 

示例 2:

輸入: 
first = "pales"
second = "pal"
輸出: False

雙指針寫法

    public boolean oneEditAway(String first, String second) {
        // 獲取兩個字符串的長度差，超過1的肯定不滿足條件直接返回false
        int len = first.length() - second.length();
        if(len < -1 || len > 1){
            return false;
        }
        // 定義差別值
        int count = 0;
        for (int i = 0, j = 0; i < first.length()&& j < second.length(); i++,j++) {
            // 如果出現(xiàn)字符不相等的情況
            if(first.charAt(i) != second.charAt(j)){
                if(len == 1){
                    // 如果first比較長，那么j指針后退一位，相當于空出當前位置交給下一次比較
                    j--;
                }else if(len == -1){
                    // 如果second比較長，那么i指針后退一位，相當于空出當前位置交給下一次比較
                    i--;
                }
                // 差別值+1
                count++;
            }
            // 差別值>1返回false
            if(count >1){
                return false;
            }
        }
        return true;
    }

編輯距離

給你兩個單詞 word1 和 word2，請你計算出將 word1 轉(zhuǎn)換成 word2 所使用的最少操作數(shù) 。
你可以對一個單詞進行如下三種操作：
插入一個字符
刪除一個字符
替換一個字符

示例 1：

輸入：word1 = "horse", word2 = "ros"
輸出：3
解釋：
horse -> rorse (將 'h' 替換為 'r')
rorse -> rose (刪除 'r')
rose -> ros (刪除 'e')

示例 2：

輸入：word1 = "intention", word2 = "execution"
輸出：5
解釋：
intention -> inention (刪除 't')
inention -> enention (將 'i' 替換為 'e')
enention -> exention (將 'n' 替換為 'x')
exention -> exection (將 'n' 替換為 'c')
exection -> execution (插入 'u')

動態(tài)規(guī)劃解法：

    public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();

        // n m 中有為0的情況
        if (n*m==0) {
            return n+m;
        }

        // 初始化狀態(tài)數(shù)組
        int[][] dp = new int[n+1][m+1];

        // 邊界初始化，每移動一個位置相當于一次操作
        for (int i = 0; i < n + 1; i++) {
            dp[i][0] = i;
        }

        for (int i = 0; i < m + 1; i++) {
            dp[0][i] = i;
        }

        // 從1開始代表第一個字符，故字符的位置為i-1
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                // ex : {"*b","*c"} 當前字符為b c
                // ex : {"*b","*c"} 對word1進行刪除b
                // ex : {"*,*c"} 刪除b后，需要判斷i-1和j
                int delete = dp[i-1][j]+1;
                // ex : {"*b","*c"} 當前字符為b c
                // ex : {"*bc","*c"} 對word1進行插入c
                // ex : {"*b,*"} 插入后c可以相當于消除，那么只需要判斷i和j-1即可
                int insert = dp[i][j-1]+1;
                // ex : {"*b","*c"} 當前字符為b c
                // ex : {"*c","*c"} 對word1進行替換c
                // ex : {"*,*"} 替換c后，需要判斷i-1和j-1
                int replace = dp[i-1][j-1];
                // 如果當前字符相等，則跳過，不相等則操作+1
                if (word1.charAt(i-1)!=word2.charAt(j-1)) {
                    replace += 1;
                }
                dp[i][j] = Math.min(insert,Math.min(delete,replace));
            }
        }
        return dp[n][m];
    }

遞歸加狀態(tài)存儲寫法：

    public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();
        // 初始化狀態(tài)數(shù)組
        int[][] dp = new int[n+1][m+1];
        return minDistanceRecursive(word1.toCharArray(),word2.toCharArray(),n,m,dp);
    }

    private int minDistanceRecursive(char[] word1, char[] word2, int n, int m, int[][] dp) {
        int count;
        // 如果n m 位置已經(jīng)有值，直接返回
        if (dp[n][m]!=0)  {
            return dp[n][m];
        }
        // n m 中有數(shù)值為0的
        if (n*m==0) {
            count = n+m;
        } else if (word1[n-1]==word2[m-1]) {
            // n m 位置的值相等，直接跳過
            count = minDistanceRecursive(word1,word2,n-1,m-1,dp);
        } else {
            // 不等，執(zhí)行插入、刪除、替換三種操作，取最小的值+1（當前操作值）
            int insert = minDistanceRecursive(word1,word2,n,m-1,dp);
            int delete = minDistanceRecursive(word1,word2,n-1,m,dp);
            int replace = minDistanceRecursive(word1,word2,n-1,m-1,dp);
            count = Math.min(insert,Math.min(delete,replace))+1;
        }
        // 狀態(tài)存儲
        dp[n][m] = count;
        return count;
    }