[Python] 3 solutions - Top down DP, Bottom up DP - O(N) in Space - Clean & Concise
\u2714\uFE0F Solution 1: Top down DP\n- Let dp(i, j) be the minimum number of operations required to convert s1[0..i-1] string to s2[0..j-1] string.\n- Then dp(
**\u2714\uFE0F Solution 1: Top down DP**\n- Let `dp(i, j)` be the minimum number of operations required to convert `s1[0..i-1]` string to `s2[0..j-1]` string.\n- Then `dp(len(s1), len(s2))` is our result.\n- To compute `dp(i, j)`:\n\t- Base case: \n\t\t- If `i == 0` then we need to insert `j` chars to convert `""` into `s2[0..j-1]`\n\t\t- If `j == 0` then we need to delete `i` chars to convert `s1[0..i-1]` into `""`.\n\t- If `s1[i-1] == s2[j-1]` then `dp(i, j) = dp(i-1, j-1)`.\n\t- Else: Choose the minimum cost among 3 operators\n\t\t- Delete: `dp(i-1, j) + 1`\n\t\t- Insert: `dp(i, j-1) + 1`\n\t\t- Replace: `dp(i-1, j-1) + 1`\n```python\nclass Solution:\n    def minDistance(self, s1: str, s2: str) -> int:\n        @lru_cache(None)\n        def dp(i, j):\n            if i == 0: return j  # Need to insert j chars\n            if j == 0: return i  # Need to delete i chars\n            if s1[i-1] == s2[j-1]:\n                return dp(i-1, j-1)\n            return min(dp(i-1, j), dp(i, j-1), dp(i-1, j-1)) + 1\n        \n        return dp(len(s1), len(s2))\n```\nComplexity:\n- Time: `O(M*N)`, where `M <= 500` is length of `s1` string, `N <= 500` is length of `s2` string.\n- Space: `O(M*N)`\n\n---\n**\u2714\uFE0F Solution 2: Bottom up DP**\n- Just convert **Top down DP** into **Bottom up DP**.\n```python\nclass Solution:\n    def minDistance(self, s1: str, s2: str) -> int:\n        m, n = len(s1), len(s2)\n        dp = [[-1] * (n+1) for _ in range(m+1)]\n        for i in range(m+1):\n            for j in range(n+1):\n                if i == 0:\n                    dp[i][j] = j  # Need to insert `j` chars to become s2[:j]\n                elif j == 0:\n                    dp[i][j] = i  # Need to delete `i` chars to become ""\n                elif s1[i-1] == s2[j-1]:\n                    dp[i][j] = dp[i-1][j-1]\n                else:\n                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1\n        return dp[m][n]\n```\nComplexity:\n- Time: `O(M*N)`, where `M <= 500` is length of `s1` string, `N <= 500` is length of `s2` string.\n- Space: `O(M*N)`\n\n---\n**\u2714\uFE0F Solution 3: Bottom up DP (Space Optimized)**\n- Since we build our dp rows by rows, we access only previous dp state `dpPrev` and current dp state `dp`.\n- So we can optimize to `O(N)` in Space Complexity.\n```python\nclass Solution:\n    def minDistance(self, s1: str, s2: str) -> int:\n        m, n = len(s1), len(s2)\n        dp, dpPrev = [-1] * (n+1), [-1] * (n+1)\n        for i in range(m+1):\n            for j in range(n+1):\n                if i == 0:\n                    dp[j] = j  # Need to insert `j` chars to become s2[:j]\n                elif j == 0:\n                    dp[j] = i  # Need to delete `i` chars to become ""\n                elif s1[i-1] == s2[j-1]:\n                    dp[j] = dpPrev[j-1]\n                else:\n                    dp[j] = min(dpPrev[j], dp[j-1], dpPrev[j-1]) + 1\n            dp, dpPrev = dpPrev, dp\n        return dpPrev[n]\n```\nComplexity:\n- Time: `O(M*N)`, where `M <= 500` is length of `s1` string, `N <= 500` is length of `s2` string.\n- Space: `O(N)`
['Dynamic Programming', 'Python3']