```
int[] prev = new int[word2.length()+1]; int[] curr = new int[word2.length()+1];
for(int j = 0; j<prev.length; j++) prev[j] = curr[j] = j;
for(int i=0;i<word1.length();i++) {
curr[0] = i+1;
for(int j=1;j<curr.length;j++) {
int sub = (word1.charAt(i)==word2.charAt(j-1))?0:1;
curr[j] = Math.min(prev[j-1]+sub, Math.min(curr[j-1]+1, prev[j]+1));
}
prev=Arrays.copyOf(curr,curr.length);
}
return curr[curr.length-1];
```

I'm using the Levenshtein Distance algorithm, the version using just two lines of the matrix of distances. As we need just the previous line to compute the current line, there is no need to store the entire matrix.

Best running time in Java 328ms.