力扣(LeetCode)72

tinysun1234 發(fā)布于2019-08-16 15:08 / 2435人閱讀

摘要：題目地址題目描述給定兩個(gè)單詞和，計(jì)算出將轉(zhuǎn)換成所使用的最少操作數(shù)。那么答案則為那么如何求呢也就是轉(zhuǎn)移方程。由定義可以知道空字符串變成任意長(zhǎng)度字符串的代價(jià)為該字符串的長(zhǎng)度，也就是說。若，那么這里的解釋是，增加了一個(gè)比較對(duì)象，變成。

題目地址：
https://leetcode-cn.com/probl...
題目描述：
給定兩個(gè)單詞 word1 和 word2，計(jì)算出將 word1 轉(zhuǎn)換成 word2 所使用的最少操作數(shù) 。

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

1.插入一個(gè)字符
2.刪除一個(gè)字符
3.替換一個(gè)字符

解答：
這一題用動(dòng)態(tài)規(guī)劃，dpi表示word1中0到i的字符所組成的字符串到word2中0到j(luò)的字符所組成的字符串的編輯距離。
那么答案則為dpword1.length
那么如何求dpi呢？也就是轉(zhuǎn)移方程。由定義可以知道空字符串變成任意長(zhǎng)度字符串的代價(jià)為該字符串的長(zhǎng)度，也就是說dp0 = j+1,dpi = i+1。這里的i，j最大分別為word1和word2的長(zhǎng)度-1。
對(duì)于dpi,若word1[i] != word2[j]，那么dpi = 1 + min(dpi-1,dpi),這里的解釋為刪除word1[i]或者刪除word2[j],并且比較word1[0-i-1]變成word2[0-j]和word1[0-i]變成word2[0-j-1]的大小，選擇小的那個(gè)。
若word1[i] == word2[j]，那么dpi = min(dpi-1,1 + min(dpi-1,dpi))這里的解釋是，增加了一個(gè)比較對(duì)象，word1[0-i-1]變成word2[0-j-1]。
java ac代碼：

class Solution {
    public int minDistance(String word1, String word2) {
        if(word1.length() == 0||word2.length() == 0)return Math.max(word1.length(),word2.length());
        int[][]dp = new int[word1.length()+1][word2.length()+1];
        for(int i = 0;i <= word1.length();i++)
            dp[i][0] = i;
        for(int j = 0;j <= word2.length();j++)
            dp[0][j] = j;
        
        for(int i = 1;i <= word1.length();i++)
            for(int j = 1;j <= word2.length();j++)
            {
                int ans = 1+Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]);
                if(word1.charAt(i-1) == word2.charAt(j-1))
                ans = Math.min(ans,dp[i-1][j-1]);
                dp[i][j] = ans;
            }
        return dp[word1.length()][word2.length()];
    }
}