Maybe Better than O(mn) - Heap solution (Python) Beats 99% [ O((m+n)log(m+n)) ? (not sure)]
\n\n\nKeep a minheap and chop off 1 character at a time. To avoid using too much space with substring splicing, we can move pointers i and j instead.\n\nKeep a 
![image](https://assets.leetcode.com/users/images/1e61e11a-f3e8-4d0a-92c3-f2565c7360b0_1623299142.487367.png)\n\n\nKeep a minheap and chop off 1 character at a time. To avoid using too much space with substring splicing, we can move pointers `i` and `j` instead.\n\nKeep a minheap with items in there form `(distance, i, j)`\nWhere `word1[:i]` and `word[:j]` have an edit distance of `distance`\n\n1. Pop from the heap to give current lowest edit distance and string index pair\n2. If word1 and word2 from pointers  `i` and `j`  are **both exactly exact same**:\n\t=>  return the `distance` , don\'t need to increment the distance anymore\n\t\n3. Do the following if `i` and `j` are unvisited (if we are visiting the same `i` and `j` again, that means the distance is not lower than previously seen, so we should ignore it)\n\t4.  if the characters at `i` and `j` match, **no change needed** , increment both word pointers but keep distance the same\n\t5.  Otherwise, increment distance and:\n\t\t6. Add **delete from word1** case (`i+1`)\n\t\t7. Add **delete from word2** case (`j+1`)\n\t\t8. Add **replace current character** case (`i+1`) and (`j+1`)\n\n```python\nclass Solution:\n    def minDistance(self, word1: str, word2: str) -> int:\n        m, n = len(word1), len(word2)\n        heap = [(0, 0, 0)]\n        seen = set()\n        \n        while heap:\n            distance, i, j = heappop(heap)\n            if word1[i:] == word2[j:]:\n                return distance\n\t\t\n            if ((i, j) not in seen):\n                seen.add((i, j))\n                if (i < m and j < n and word1[i] == word2[j]):\n                    heappush(heap, (distance, i+1, j+1))\n                else:\n                    for di, dj in (1,0), (0,1), (1,1):\n                        next_i, next_j = i+di, j+dj\n                        if (next_i <= m and next_j <= n):\n                            heappush(heap, (distance+1, next_i, next_j))\n```\n\n\n**Time complexity**\n\nAssuming length of `word1` is `m` and length of `word2` is `n`\nFor each of the `m` characters and `n` that modify the heap at most 3 times. Thus the heap size can be at most `(m+n)*3` = `m+n`\n\nThus all heap operations are  `O(log(m+n))`\nWhich is done for all `m+n` items thus `O((m+n)log(m+n))`\nIf this is true, than this is better than the typical `O(mn)` DP solution.\nThough it might just be `O(mn*log(mn))` with a good average case...\n\n\n
['Heap (Priority Queue)', 'Python', 'Python3']