```
public int minDistance(String word1, String word2) {
int n = word1.length() < word2.length() ? word1.length() : word2.length();
int[] counts = new int[n + 1];
counts[0] = -1;
int maxCount = 0;
for(int i = 0; i < word1.length(); i++){
for(int t = maxCount + 1; t > 0; t--){
int start = counts[t - 1] + 1;
int end = -1;
if(t == maxCount + 1)
end = word2.length();
else
end = counts[t];
for(int j = start; j < end; j++){
if(word1.charAt(i) == word2.charAt(j)){
counts[t] = j;
if(t == maxCount + 1)
maxCount++;
break;
}
}
}
if(maxCount == n)
break;
}
return word1.length() + word2.length() - 2 * maxCount;
}
```