[LintCode/LeetCode] Edit Distance

snowell 發布于2019-08-14 15:29 / 2982人閱讀

摘要：構造數組，是的，是的，是將位的轉換成位的需要的步數。初始化和為到它們各自的距離，然后兩次循環和即可。

Problem

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

Insert a character
Delete a character
Replace a character

Example

Given word1 = "mart" and word2 = "karma", return 3.

Note

構造dp[i][j]數組，i是word1的index+1，j是word2的index+1，dp[i][j]是將i位的word1轉換成j位的word2需要的步數。初始化dp[i][0]和dp[0][i]為dp[0][0]到它們各自的距離i，然后兩次循環i和j即可。
理解三種操作：insertion是完成i-->j-1之后，再插入一位才完成i-->j；deletion是完成i-->j之后，發現i多了一位，所以i-1-->j才是所求，需要再刪除一位才完成i-->j；而replacement則是換掉word1的最后一位，即之前的i-1-->j-1已經完成，如果word1的第i-1位和word2的第j-1位相等，則不需要替換操作，否則要替換一次完成i-->j。

Solution

public class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m+1][n+1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0) dp[i][j] = j;
                else if (j == 0) dp[i][j] = i;
                else {
                    int insert = dp[i][j-1] + 1;
                    int delete = dp[i-1][j] + 1;
                    int replace = dp[i-1][j-1] + (word1.charAt(i-1) == word2.charAt(j-1) ? 0 : 1);
                    dp[i][j] = Math.min(insert, Math.min(delete, replace));
                }
            }
        }
        return dp[m][n];
    }
}

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/65798.html

[LintCode/LeetCode] Best Meeting Point

Problem A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance ...

morgan 2019-08-16 12:37 評論0 收藏0
[LintCode/LeetCode] Jump Game I & II

摘要：建立動規數組，表示從起點處到達該點的可能性。循環結束后，數組對所有點作為終點的可能性都進行了賦值。和的不同在于找到最少的步數。此時的一定是滿足條件的最小的，所以一定是最優解。 Jump Game Problem Given an array of non-negative integers, you are initially positioned at the first index...

rose 2019-08-14 15:27 評論0 收藏0
[Leetcode] One Edit Distance 編輯距離為一

摘要：比較長度法復雜度時間空間思路雖然我們可以用的解法，看是否為，但中會超時。這里我們可以利用只有一個不同的特點在時間內完成。 One Edit Distance Given two strings S and T, determine if they are both one edit distance apart. 比較長度法復雜度時間 O(N) 空間 O(1) 思路雖然我們可以用...

lewinlee 2019-08-14 12:48 評論0 收藏0
Leetcode[161] One Edit Distance

摘要：復雜度思路考慮如果兩個字符串的長度，是肯定當兩個字符串中有不同的字符出現的時候，說明之后的字符串一定要相等。的長度比較大的時候，說明的時候，才能保證距離為。 LeetCode[161] One Edit Distance Given two strings S and T, determine if they are both one edit distance apart. Stri...

周國輝 2019-08-14 15:58 評論0 收藏0
LeetCode[72] Edit Distance

摘要：復雜度思路考慮用二維來表示變換的情況。如果兩個字符串中的字符相等，那么如果兩個字符串中的字符不相等，那么考慮不同的情況表示的是，從字符串到的位置轉換到字符串到的位置，所需要的最少步數。 LeetCode[72] Edit Distance Given two words word1 and word2, find the minimum number of steps require...

call_me_R 2019-08-14 15:00 評論0 收藏0