Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
b) Delete a character
c) Replace a character
Solution:O(m*n)
public class Solution {
public int minDistance(String word1, String word2) {
if(word1.equals(word2))
return 0;
if(word1.length() == 0)
return word2.length();
if(word2.length() == 0)
return word1.length();
if(word1.length() == 1 && word2.length() == 1)
return 1;
int len1 = word1.length();
int len2 = word2.length();
int [][] f = new int[len1+1][len2+1];
for(int i=0; i<= len1;i++){
for(int j=0; j<= len2;j++){
if(i == 0){
f[i][j] = j;
}else if(j == 0){
f[i][j] = i;
}else if(word1.charAt(i-1) == word2.charAt(j-1)){
f[i][j] = f[i-1][j-1];
}else{
f[i][j] = Math.min(f[i-1][j-1], Math.min(f[i-1][j], f[i][j-1]))+1;
}
}
}
return f[len1][len2];
}
}
Key Concept: DP classic
沒有留言:
張貼留言