题意
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
输出word1经过几次单字符变换可以变为word2。变换单字符可以使用插入、删除、替换。
思路
经典的动态规划问题，一维数组就可以解，不过二位数组思路比较见简单。
dp[i][j]表示word1字串0到i，变换到word2字串0到j需要多少次。
dp[i][j]=min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + w1[i]==w2[j] ? 1 : 0)
解
public int minDistance(String word1
, String word2
) {
int[][] minDist
= new int[word1
.length() + 1][word2
.length() + 1];
for (int i
= 1; i
<= word1
.length(); i
++)
minDist
[i
][0] = i
;
for (int j
= 1; j
<= word2
.length(); j
++)
minDist
[0][j
] = j
;
for (int i
= 1; i
<= word1
.length(); i
++) {
for (int j
= 1; j
<= word2
.length(); j
++) {
minDist
[i
][j
] = Math
.min(Math
.min(
minDist
[i
][j
- 1] + 1,
minDist
[i
- 1][j
] + 1),
minDist
[i
- 1][j
- 1] + (word1
.charAt(i
- 1) == word2
.charAt(j
- 1) ? 0 : 1)
);
}
}
return minDist
[word1
.length()][word2
.length()];
}
