```
public int minDistance(String word1, String word2) {
int[] dp = new int[word2.length()];
int lcs = 0;
for(int i = 0; i < word1.length(); i++){
int cur_max = 1;
for(int j = 0; j < word2.length(); j++){
int temp = dp[j];
if(word2.charAt(j) == word1.charAt(i)) dp[j] = cur_max;
cur_max = Math.max(temp+1, cur_max);
lcs = Math.max(lcs, dp[j]);
}
}
return word1.length() - lcs + word2.length() - lcs;
}
```

Use O(n) space, in i-th iteration over word1, update max possible length of common subsequence end up with word1.charAt(i) in word2 and store in the dp array.