LeetCode 72. Edit Distance(java)

5404 단어 dpString
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:
a) Insert a character b) Delete a character c) Replace a character
사고방식: 동적 기획 해
DP: dp[i][j]  word1  i  word2  j          。
case1 : (word1[i] == word2[j]) dp[i][j] = dp[i-1][j-1];
case2 : (word1[i] == word2[j]) insert: dp[i][j] = dp[i][j-1];
                               delete: dp[i][j] = dp[i-1][j];
                               replace: dp[i][j] = dp[i-1][j-1];
base case: dp[i][0] = dp[0][i] = i;

코드:
public int minDistance(String word1, String word2) {
        if (word1.length() == 0) return word2.length();
        if (word2.length() == 0) return word1.length();
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) dp[i][0] = i; 
        for (int i = 0; i < n; i++) dp[0][i] = i;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i) == word2.charAt(j)) {
                    dp[i][j] = dp[i - 1][j -1 ];
                } else {
                    int insert = dp[i][j - 1];
                    int delete = dp[i - 1][j];
                    int replace = dp[i -1][j - 1];
                    dp[i][j] = Math.min(insert, Math.min(delete, replace));
                    dp[i][j]++;
                }
            }
        }
        return dp[m][n];
    }
//     dp  ,         :              m*n       ,pre             ,temp               ,                。
    public int minDistance(String word1, String word2) {
        if (word1.length() == 0) return word2.length();
        if (word2.length() == 0) return word1.length();
        int m = word1.length(), n = word2.length();
        int[] dp = new int[n + 1];
        for (int i = 0; i <= n; i++) dp[i] = i; 
        for (int i = 1; i <= m; i++) {
            int temp = 0, pre = i - 1;
            dp[0] = i;
            for (int j = 1; j <= n; j++) {
                temp = dp[j];
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[j] = pre;
                } else {
                    dp[j] = Math.min(dp[j], Math.min(dp[j-1], pre));
                    dp[j]++;
                }
                pre = temp;
            }
        }
        return dp[n];
    }

좋은 웹페이지 즐겨찾기