Solution
C++ []\nclass Solution {\npublic:\n    vector<vector<int>> dp;\n    \n    int solve(int i, int j, string &s, string &t){\n        if(i<0 && j<0)\n            re
```C++ []\nclass Solution {\npublic:\n    vector<vector<int>> dp;\n    \n    int solve(int i, int j, string &s, string &t){\n        if(i<0 && j<0)\n            return 0;\n        \n        if(i < 0 && j>=0){\n            return j+1;\n        }\n        \n        if(i>=0 && j<0){\n            return i+1;\n        }\n        \n        if(dp[i][j] != -1)\n            return dp[i][j];\n        \n        int l = 1000, r = 1000, z = 1000, p = 1000;\n        if(s[i] == t[j]){\n            l = solve(i-1,j-1,s,t);\n        }\n        else{\n            r = 1 + solve(i-1,j,s,t);\n            z = 1 + solve(i-1,j-1,s,t);\n            p = 1 + solve(i,j-1,s,t);\n        }\n        \n        return dp[i][j] = min(l,min(r,min(z,p)));\n    }\n    \n    \n    int minDistance(string s, string t) {\n        dp.resize(s.size()+1,vector<int>(t.size()+1,-1));\n        return solve(s.size(),t.size(),s,t);\n    }\n};\n```\n\n```Python3 []\nclass Solution:\n    def minDistance(self, word1: str, word2: str) -> int:\n        n = len(word1)\n        m = len(word2)\n        \n        to_visit = [(0, 0)]\n        visited = set()\n        dist = 0\n        while to_visit:\n            nxt_lvl = []\n            while to_visit:\n                i, j = to_visit.pop()\n                if (i, j) in visited:\n                    continue\n                while i < n and j < m and word1[i] == word2[j]:\n                    i += 1\n                    j += 1\n                if i == n and j == m:\n                    return dist\n                if (i, j + 1) not in visited:\n                    nxt_lvl.append((i, j + 1))\n                if (i + 1, j) not in visited:\n                    nxt_lvl.append((i + 1, j))\n                if (i + 1, j + 1) not in visited:\n                    nxt_lvl.append((i + 1, j + 1))\n                visited.add((i, j))\n            dist += 1\n            to_visit = nxt_lvl\n```\n\n```Java []\nclass Solution {\n    public int minDistance(String word1, String word2) {\n        if (word1.length() < word2.length()) {\n            return minDistance(word2, word1);\n        }\n        char[] w1 = word1.toCharArray(), w2 = word2.toCharArray();\n        int[] dp = new int[w2.length];\n        int last = 0;\n        int diag = 0;\n        for (int i = 0; i < dp.length; i++) {\n            dp[i] = dp.length - i;\n        }\n        for (int i = w1.length - 1; i > -1; i--) {\n            last = w1.length - i;\n            diag = w1.length - 1 - i;\n            for (int j = w2.length - 1; j > -1; j--) {\n                int tmp = dp[j];\n                if (w1[i] == w2[j]) {\n                    last = dp[j] = diag;\n                } else {\n                    last = dp[j] = Math.min(diag, Math.min(dp[j], last)) + 1;\n                }\n                diag = tmp;\n            }\n        }\n        return last;\n    }\n}\n```\n
['C++', 'Java', 'Python3']