題目鏈接：https://leetcode.com/problems/edit-distance/description/恬偷。
字符串相關(guān)的算法題的求解，很多需要用到動(dòng)態(tài)規(guī)劃思想渴逻。動(dòng)態(tài)規(guī)劃本質(zhì)以空間換時(shí)間，記錄發(fā)生過的狀態(tài)音诫，用于后面狀態(tài)的處理惨奕，避免重復(fù)計(jì)算。難點(diǎn)在于狀態(tài)轉(zhuǎn)換規(guī)律的總結(jié)纽竣。
回到編輯距離的問題上來。定義二維矩陣dp茧泪，dp[i][j]表示長度為i和j的兩個(gè)字符串的編輯距離蜓氨。接下來，我們探討dp[i][j]與dp[i-1][j-1]的遞推關(guān)系队伟，假定第一個(gè)字符串（word1）的末字符為“x”穴吹，第二個(gè)字符串（word2）的末字符為“y”，如下圖：
Edit Distance
分析如下：
- 如果x == y嗜侮，dp[i][j] == dp[i-1][j-1];
- 如果x != y港令，word1字符串插入y，則dp[i][j] = dp[i][j-1] + 1;
- 如果x != y锈颗，word1字符串刪除x顷霹，則dp[i][j] = dp[i-1][j] + 1;
- 如果x != y，word1字符串替換x為y击吱，則dp[i][j] = dp[i-1][j-1] + 1;
- 所以淋淀，當(dāng)x !=y，dp[i][j]為這三種情形的最小值覆醇。
還有一點(diǎn)朵纷，dp二維數(shù)組的初始化：
dp[i][0] = i，dp[0][j] = j永脓。
Accept代碼如下:
class Solution {
public int minDistance(String word1, String word2) {
// +1是為了從len=0的字符串算起
int[][] dp = new int[word1.length() + 1][word2.length() + 1];
// dp二維數(shù)組的初始化
dp[0][0] = 0;
for (int i=1; i<word1.length()+1; i++)
{
dp[i][0] = i;
}
for (int i=1; i<word2.length()+1; i++)
{
dp[0][i] = i;
}
// dp的關(guān)系遞推
for (int i=1; i<word1.length()+1; i++)
for(int j=1; j<word2.length()+1; j++)
{
if(word1.charAt(i-1) == word2.charAt(j-1))
{
dp[i][j] = dp[i-1][j-1];
}
else
{
dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
}
}
return dp[word1.length()][word2.length()];
}
}
