72. Edit Distance - Medium

前往題目

思路

1. 二維dp，分別是i和j，word1與word2的指針
2. i, j代表取word1和word2的前i和前j個
3. 如此一來，base case就是word1取了前幾個，word2取0個，那每次都會等於i；相同的，word1取0個，word2取了前幾個，每次都等於j
4. 從左到右一個一個看，當前的字母都一樣的話那代表什麼都不用做，所以就等於上次(i - 1, j - 1)的操作數
5. 如果不一樣，有三種操作

也是腦筋急轉彎的一題

Code

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

        int[][] dp = new int[m + 1][n + 1];

        // For easier pointer operation
        word1 = "#" + word1;
        word2 = "#" + word2;

        // Base case
        for (int i = 0; i <= m; ++i) {
            // 加入i個相應字符
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; ++j) {
            // 加入j個相應字符
            dp[0][j] = j;
        }

        // 因為0, 0是base case所以從1開始
        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 {
                    // +1是因為操作了一次
                    dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, // 替換
                               Math.min(dp[i - 1][j] + 1, // 刪除
                                        dp[i][j - 1] + 1)); // 插入
                }
            }
        }

        return dp[m][n]; // 兩個指針都抵達終點的操作數
    }
}