LeetCode The Hard Way - 0072 - Edit Distance (Hard)
\uD83D\uDD34 Check out LeetCode The Hard Way for more solution explanations and tutorials. \n\uD83D\uDFE0 Check out our Discord Study Group for live discussion.
\uD83D\uDD34 Check out [LeetCode The Hard Way](https://wingkwong.github.io/leetcode-the-hard-way/) for more solution explanations and tutorials. \n\uD83D\uDFE0 Check out our [Discord Study Group](https://discord.gg/Nqm4jJcyBf) for live discussion.\n\uD83D\uDFE2 Give a star on [Github Repository](https://github.com/wingkwong/leetcode-the-hard-way) and upvote this post if you like it.\n\uD83D\uDD35 Check out [Screencast](https://www.youtube.com/watch?v=5by6g9bxPW8&list=PLBu4Bche1aEU-8z7xl3-B9lfw_DJtT_xs&index=26) if you are interested.\n\n---\n\nEdit distance is a classic DP problem. It is used to quantify the dissimilarity of two given strings by counting the minimum possible number of operations required to transform one string into the other. \n\nGiven that the constraints, we assume that a O(m * n) solution would pass. \n\nLet\'s define ``dp[i][j]`` as the minimum edit distance between the first i character of ``word1`` and the first ``j`` characters of ``word2``. In example 1, ``dp[3][2]``would be the edit distance between ``word1[1..3]`` (HOR) and ``word2[1..2]``(RO). \n\nIf the last character is the same, then ``dp[i][j]`` would be ``dp[i - 1][j - 1]`` because we don\'t need to perform any operation. Otherwise, we need to perform either one. There are three possible ways to do the transformation.\n\n- We can transform ``word1[1..i]`` to ``word2[1..j-1]`` by adding ``word2[j]`` afterwards to get ``word2[1..j]``.\n- We can transform ``word1[1..i-1]`` to ``word2[1..j]`` by deleting ``word1[i]``.\n- We can transform ``word1[1..i-1]`` to ``word2[1..j-1]`` by exchanging the original ``word1[i]`` for ``word2[j]``.\n\nTherefore, the transition would be ``dp[i][j] = 1 + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])`` if ``word1[i]`` is not equal to ``word2[j]``.\n\nWhat is the base case then? The base case is simply an edit distance between the empty string and non-empty string, i.e. ``dp[i][0] = i`` and ``dp[0][j] = j``. The answer would be ``dp[m][n]``. This algorithm is also known as Wagner\u2013Fischer algorithm.\n\n![image](https://assets.leetcode.com/users/images/00774ca9-da4e-4873-a6c5-9d7596b60b19_1642775600.173192.png)\n\nTime Complexity: O(m * n)\nSpace Complexity: O(m * n)\n\n```\nclass Solution {\npublic:\n    int minDistance(string word1, string word2) {\n        int m = (int) word1.size();\n        int n = (int) word2.size();\n        int dp[m + 1][n + 1];\n        memset(dp, 0, sizeof(dp));\n        for (int i = 1; i <= m; i++) dp[i][0] = i;\n        for (int j = 1; j <= n; j++) dp[0][j] = j;\n        for (int i = 1; i <= m; i++){\n            for(int j = 1; j <= n; j++){\n                if(word1[i - 1] == word2[j - 1]) { // a = b\n                    dp[i][j] = dp[i - 1][j - 1]; \n                } else {\n                    // find out the min cost for all three actions\n                    dp[i][j] = 1 + min({\n                        dp[i - 1][j - 1], // replace a with b\n                        dp[i - 1][j],     // delete a\n                        dp[i][j - 1]      // insert b after a\n                    });\n                }\n            }\n        }\n        return dp[m][n];\n    }\n};\n```\n\n```py\nclass Solution:\n    def minDistance(self, word1: str, word2: str) -> int:\n        m, n = len(word1), len(word2)\n        dp = [[0] * (n + 1) for _ in range(m + 1)]\n        for i in range(1, m + 1): dp[i][0] = i\n        for j in range(1, n + 1): dp[0][j] = j\n        for i in range(1, m + 1):\n            for j in range(1, n + 1):\n                if word1[i - 1] == word2[j - 1]:\n                    # a == b\n                    dp[i][j] = dp[i - 1][j - 1]\n                else:\n                    # find out the min cost for all three actions\n                    # dp[i - 1][j - 1]: replace a with b\n                    # dp[i - 1][j]: delete a\n                    # dp[i - 1][j]: insert b after a\n                    dp[i][j] = 1 + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])\n        return dp[m][n]\n```
[]