Please Google "myers diff algorithm"!

I wrote the code about one year ago and don't know what the hack is going now. Sorry...

As I know, it is fastest discovered LCS algorithm.

```
class Solution:
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
return (len(word1) + len(word2) - self.diff(word1, word2))
def diff(self, a, b):
max_supply = len(a) + len(b)
max_x_nth_k = {1: 0}
for supply in range(max_supply + 1):
for nth_k in range(-supply, supply + 1, 2):
if nth_k == -supply or (nth_k != supply and max_x_nth_k[nth_k - 1] < max_x_nth_k[nth_k + 1]):
x = max_x_nth_k[nth_k + 1]
else:
x = max_x_nth_k[nth_k - 1] + 1
y = x - nth_k
while x < len(a) and y < len(b) and a[x] == b[y]:
x += 1
y += 1
max_x_nth_k[nth_k] = x
if x >= len(a) and y >= len(b):
return (len(a) + len(b) - supply) // 2
```