72. Edit Distance with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n- We use a 2D dp array dp with dimensions (m+1) x (n+1), where m and n ar
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n- We use a 2D dp array dp with dimensions (m+1) x (n+1), where m and n are the lengths of word1 and word2, respectively.\n- dp[i][j] represents the minimum number of operations required to convert the first i characters of word1 to the first j characters of word2.\n- Initially, if one of the strings is empty, the min number of operations is inserting all characters from the other string, so we fill the first row and first column with i and j, respectively.\n- For each i and j, we compare the characters word1[i-1] and word2[j-1]. If they are the same, we don\'t need to perform any operation, so dp[i][j] takes the value of dp[i-1][j-1]. If they are different, we find the minimum of three operations: replace, insert, delete, and update dp[i][j] accordingly.\n- Finally, the minimum number of operations required is stored in dp[m][n].\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def minDistance(self, word1: str, word2: str) -> int:\n        m, n = len(word1), len(word2)\n        dp = [[0 for j in range(n+1)] for i in range(m+1)]\n        \n        # if one of the strings is empty, the min number of operations is inserting all characters from the other string\n        for i in range(1, m+1):\n            dp[i][0] = i\n        for j in range(1, n+1):\n            dp[0][j] = j\n        \n        for i in range(1, m+1):\n            for j in range(1, n+1):\n                # if the characters are the same, we don\'t need to perform any operation\n                if word1[i-1] == word2[j-1]:\n                    dp[i][j] = dp[i-1][j-1]\n                else:\n                    # find the minimum of three operations: replace, insert, delete\n                    dp[i][j] = min(dp[i-1][j-1]+1, dp[i-1][j]+1, dp[i][j-1]+1)\n        \n        return dp[m][n]\n\n```
['Python', 'Python3']