1+ /*
2+ Author: King, wangjingui@outlook.com
3+ Date: Dec 25, 2014
4+ Problem: Edit Distance
5+ Difficulty: Medium
6+ Source: https://oj.leetcode.com/problems/edit-distance/
7+ Notes:
8+ 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.)
9+ You have the following 3 operations permitted on a word:
10+ a) Insert a character
11+ b) Delete a character
12+ c) Replace a character
13+
14+ Solution: Dynamic Programming.
15+ 1. Time: O(mn) Space: O(mn)
16+ 2. Time: O(mn) Space: O(n);
17+ */
18+ public class Solution {
19+ public int minDistance_1 (String word1 ,String word2 ) {
20+ if (word1 ==word2 )return 0 ;
21+ int len1 =word1 .length ();
22+ int len2 =word2 .length ();
23+ int [][]dp =new int [len1 +1 ][len2 +1 ];
24+
25+ for (int i =0 ;i <=len1 ;i ++)
26+ dp [i ][0 ] =i ;
27+ for (int i =0 ;i <=len2 ;i ++)
28+ dp [0 ][i ] =i ;
29+
30+ for (int i =1 ;i <=len1 ;i ++){
31+ for (int j =1 ;j <=len2 ;j ++){
32+ if (word1 .charAt (i -1 )==word2 .charAt (j -1 ))dp [i ][j ] =dp [i -1 ][j -1 ];
33+ else {
34+ dp [i ][j ] =Math .min (dp [i -1 ][j ],Math .min (dp [i ][j -1 ],dp [i -1 ][j -1 ]))+1 ;
35+ }
36+ }
37+ }
38+ return dp [len1 ][len2 ];
39+ }
40+ public int minDistance (String word1 ,String word2 ) {
41+ if (word1 ==word2 )return 0 ;
42+ int len1 =word1 .length ();
43+ int len2 =word2 .length ();
44+ int []dp =new int [len2 +1 ];
45+
46+ for (int i =0 ;i <=len2 ;i ++)
47+ dp [i ] =i ;
48+
49+ for (int i =1 ;i <=len1 ;i ++){
50+ int upperLeftBak =dp [0 ];
51+ dp [0 ] =i ;
52+ for (int j =1 ;j <=len2 ;j ++){
53+ int upperLeft =upperLeftBak ;
54+ upperLeftBak =dp [j ];
55+ if (word1 .charAt (i -1 )==word2 .charAt (j -1 ))dp [j ] =upperLeft ;
56+ else {
57+ dp [j ] =Math .min (dp [j ],Math .min (dp [j -1 ],upperLeft ))+1 ;
58+ }
59+ }
60+ }
61+ return dp [len2 ];
62+ }
63+ }
