?? 算法刷題專欄 | 面試必備算法 | 面試高頻算法 ??
?? 越難的東西,越要努力堅持，因為它具有很高的價值，算法就是這樣?
?? 作者簡介：碩風(fēng)和煒，CSDN-Java領(lǐng)域新星創(chuàng)作者??，保研|國家獎學(xué)金|高中學(xué)習(xí)JAVA|大學(xué)完善JAVA開發(fā)技術(shù)棧|面試刷題|面經(jīng)八股文|經(jīng)驗分享|好用的網(wǎng)站工具分享??????
?? 恭喜你發(fā)現(xiàn)一枚寶藏博主,趕快收入囊中吧??
?? 人生如棋，我愿為卒，行動雖慢，可誰曾見我后退一步？????

?? 題目鏈接

• 72. 編輯距離

? 題目描述

給你兩個單詞 word1 和 word2， 請返回將 word1 轉(zhuǎn)換成 word2 所使用的最少操作數(shù) 。

你可以對一個單詞進(jìn)行如下三種操作：

插入一個字符
刪除一個字符
替換一個字符

示例 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’)

提示：

0 <= word1.length, word2.length <= 500
word1 和 word2 由小寫英文字母組成

?? 求解思路&實現(xiàn)代碼&運行結(jié)果

? 暴力法

?? 求解思路

1. 這道題目的求解思路其實題目已經(jīng)告訴我們了，每一步的選擇可以值插入、可以是刪除、也可以是替換，我們最后求的是通過三種方式將s1變成s2的最少次數(shù)。
2. 怎么求解呢？我們先想我們要求解什么，也就是最大的問題的規(guī)模？要求解的結(jié)果我們上面也說了，比如第一次我們選擇了插入、刪除、或者是替換，下一次呢，還是原來的求解思路，那么怎么求解呢？是不是顯而易見了呢？我們直接通過遞歸求解即可。

?? 實現(xiàn)代碼

class Solution {
    public int minDistance(String word1, String word2) {
        char[] c1=word1.toCharArray();
        char[] c2=word2.toCharArray();
        return process(0,0,c1,c2);
    }

    public int process(int i,int j,char[] c1,char[] c2){
        if(i==c1.length){
            return c2.length-j;
        }
        if(j==c2.length){
            return c1.length-i;
        }
        if(c1[i]==c2[j]) return process(i+1,j+1,c1,c2);
        else{
            int p1=process(i,j+1,c1,c2);
            int p2=process(i+1,j,c1,c2);
            int p3=process(i+1,j+1,c1,c2);
            return Math.min(Math.min(p1,p2),p3)+1;
        }
    }
}

?? 運行結(jié)果

時間超限了，不要緊張，我們來繼續(xù)優(yōu)化它！

? 記憶化搜索

?? 求解思路

1. 因為在遞歸的過程中，會重復(fù)的出現(xiàn)一些多次計算的結(jié)果，我們通過開辟一個數(shù)組，將結(jié)果提前緩存下來，算過的直接返回，避免重復(fù)計算，通過空間來去換我們的時間。

?? 實現(xiàn)代碼

class Solution {

    private int[][] dp;

    public int minDistance(String word1, String word2) {
        char[] c1=word1.toCharArray();
        char[] c2=word2.toCharArray();
        int m=c1.length,n=c2.length;
        dp=new int[m][n];
        for(int i=0;i<m;i++) Arrays.fill(dp[i],-1);
        return process(0,0,c1,c2);
    }

    public int process(int i,int j,char[] c1,char[] c2){
        if(i==c1.length){
            return c2.length-j;
        }
        if(j==c2.length){
            return c1.length-i;
        }
        if(dp[i][j]!=-1) return dp[i][j];
        if(c1[i]==c2[j]) return dp[i][j]=process(i+1,j+1,c1,c2);
        else{
            int p1=process(i,j+1,c1,c2);
            int p2=process(i+1,j,c1,c2);
            int p3=process(i+1,j+1,c1,c2);
            return dp[i][j]=Math.min(Math.min(p1,p2),p3)+1;
        }
    }
}

?? 運行結(jié)果

我們發(fā)現(xiàn)，通過加一個緩存表，時間復(fù)雜度發(fā)生了翻天覆地的變化，真是不可思議！

? 動態(tài)規(guī)劃

?? 求解思路

1. 有了遞歸，有了記憶化搜索，接下來就是動態(tài)規(guī)劃了，直接上手。

?? 實現(xiàn)代碼

class Solution {

    private int[][] dp;

    public int minDistance(String word1, String word2) {
        char[] c1=word1.toCharArray();
        char[] c2=word2.toCharArray();
        int m=c1.length,n=c2.length;
        dp=new int[m+1][n+1];
        for(int i=0;i<=n;i++) dp[m][i]=n-i;
        for(int i=0;i<=m;i++) dp[i][n]=m-i;
        for(int i=m-1;i>=0;i--){
            for(int j=n-1;j>=0;j--){
                if(c1[i]==c2[j]) dp[i][j]=dp[i+1][j+1];
                else dp[i][j]=Math.min(Math.min(dp[i][j+1],dp[i+1][j]),dp[i+1][j+1])+1;
            }
        }
        return dp[0][0];
    }
}

?? 運行結(jié)果

搞定！

?? 共勉

文章來源地址http://www.zghlxwxcb.cn/news/detail-455141.html

到了這里，關(guān)于【LeetCode:72. 編輯距離 | 暴力遞歸=＞記憶化搜索=＞動態(tài)規(guī)劃 】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！