My code:
public class Solution {
public int minDistance(String word1, String word2) {
if (word1 == null || word2 == null)
return -1;
else if (word1.length() == 0)
return word2.length();
else if (word2.length() == 0)
return word1.length();
else if (word1.equals(word2))
return 0;
int len1 = word1.length();
int len2 = word2.length();
/** dp[i][j] means the distance between word1[0, 0 + len1) and word2[0, 0 + len2) */
int[][] dp = new int[len1 + 1][len2 + 1];
for (int i = 0; i <= len1; i++)
dp[i][0] = i;
for (int i = 0; i <= len2; i++)
dp[0][i] = i;
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
char c1 = word1.charAt(i - 1);
char c2 = word2.charAt(j - 1);
if (c1 == c2) {
dp[i][j] = dp[i - 1][j - 1];
}
else {
int delete = dp[i - 1][j] + 1;
int insert = dp[i][j - 1] + 1;
int replace = dp[i - 1][j - 1] + 1;
dp[i][j] = Math.min(delete, Math.min(insert, replace));
}
}
}
return dp[len1][len2];
}
}
這道題木既昨天 scramble string之后，再次刷新我三觀逐样。蜗字。打肝。
DP就像是一臺參透天地規(guī)則的機(jī)器。放在那里跑挪捕。雖然笨粗梭，慢，但是级零，最終結(jié)果断医，
一定會出來！
一定是正確的奏纪！
就是是圖靈機(jī)鉴嗤。就像那部電影里破譯電報密碼的機(jī)器。
雖然笨重序调，落后醉锅，但是，結(jié)果一定會出來炕置。
說了這么多荣挨，實在是感嘆DP的偉大。
雖然也知道做他的思路朴摊。但是默垄，真的想不出
dp[i][j] 的具體物理意義。這真的是思維高度不同甚纲。
這道題目口锭。
dp[i][j] 表示 word1.substring(0, i) and word2.substring(0, j) 的distance
即word1從開頭，長度為i的子串介杆，和word2從開頭鹃操，長度為j的子串，之間的distance春哨。
dp[i][j]
所以荆隘，
dp[0][j] = j
dp[i][0] = i
假設(shè)現(xiàn)在一個長度分別為 i, j 的子串。那么赴背，
dp[i][j] 等于多少呢椰拒？
或者說，他可以由哪幾個變化得到呢凰荚？
三個燃观，
delete, insert, replace
假設(shè)， c1 = word1.charAt(i); c2 = word2.charAt(j);
if c1 == c2 -> dp[i][j] = dp[i - 1][j - 1];
即便瑟，word1[0, i - 1) 變化到 word2[0, j - 1) 的步數(shù)
與 word1[0, i) 變化到 word2[0, j)的步數(shù)相同缆毁。 因為末尾字母相同。
這也是變化最小的步數(shù)到涂。
if c1 != c2
那么脊框，就需要多點變化了颁督。三種變化，上面說了缚陷。
假設(shè)末尾字母分別是 x适篙， y
-------x
-----------y
如果是delete
要從word1變到word2，那么把x刪除箫爷，再從word1[0, i - 1) 變到 word2[0, j)
所以，delete變化需要的步數(shù)聂儒，
delete = dp[i - 1][j] + 1;
如果是insert
那么虎锚，在word1末尾，插入y衩婚，或者說窜护，
先將 word1[0, i) 變到word2[0, j - 1), 然后word1末尾再插入y，就行了非春。
所以柱徙，insert變化需要的步數(shù)，
insert = dp[i][j - 1] + 1;
如果是replace奇昙，直接把x換成y护侮，
所以，replace變化需要的步數(shù)储耐，
replace = dp[i - 1][j - 1] + 1;
然后找出 這三個步驟操作的步數(shù)中的最小值羊初，作為dp[i][j]
然后一步步往下走。
參考網(wǎng)頁：
http://www.programcreek.com/2013/12/edit-distance-in-java/
真的想不出來什湘。长赞。
Anyway, Good luck, Richardo!
My code:
public class Solution {
public int minDistance(String word1, String word2) {
if (word1 == null || word2 == null) {
return -1;
}
int row = word1.length() + 1;
int col = word2.length() + 1;
int[][] dp = new int[row][col];
for (int i = 1; i < row; i++) {
dp[i][0] = i;
}
for (int i = 1; i < col; i++) {
dp[0][i] = i;
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
int delete = dp[i][j - 1] + 1;
int add = dp[i - 1][j] + 1;
int replace = dp[i - 1][j - 1];
if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
replace += 1;
}
dp[i][j] = Math.min(delete, Math.min(add, replace));
}
}
return dp[row - 1][col - 1];
}
}
還是靠自己做出來了，感覺和 wildcard matching 很類似
-----i
------j
- delete: dp[i - 1][j] + 1, delete i
- add: dp[i][j - 1] + 1, add i + 1 = j
- replace: dp[i - 1][j - 1] + i == j ? 0 : 1, replace j with i if necessary
Anyway, Good luck, Richardo闽撤！ -- 08/17/2016
