forked from leetcoders/LeetCode-Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathEditDistance.java
More file actions
63 lines (58 loc) · 1.97 KB
/
EditDistance.java
File metadata and controls
63 lines (58 loc) · 1.97 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/*
Author: King, wangjingui@outlook.com
Date: Dec 25, 2014
Problem: Edit Distance
Difficulty: Medium
Source: https://oj.leetcode.com/problems/edit-distance/
Notes:
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
Solution: Dynamic Programming.
1. Time: O(mn) Space: O(mn)
2. Time: O(mn) Space: O(n);
*/
public class Solution {
public int minDistance_1(String word1, String word2) {
if(word1==word2) return 0;
int len1 = word1.length();
int len2 = word2.length();
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++){
if(word1.charAt(i-1)==word2.charAt(j-1)) dp[i][j] = dp[i-1][j-1];
else{
dp[i][j] = Math.min(dp[i-1][j],Math.min(dp[i][j-1],dp[i-1][j-1]))+1;
}
}
}
return dp[len1][len2];
}
public int minDistance(String word1, String word2) {
if(word1==word2) return 0;
int len1 = word1.length();
int len2 = word2.length();
int[] dp = new int[len2+1];
for(int i=0;i<=len2;i++)
dp[i] = i;
for(int i=1;i<=len1;i++){
int upperLeftBak = dp[0];
dp[0] = i;
for(int j=1;j<=len2;j++){
int upperLeft = upperLeftBak;
upperLeftBak = dp[j];
if(word1.charAt(i-1)==word2.charAt(j-1)) dp[j] = upperLeft;
else{
dp[j] = Math.min(dp[j],Math.min(dp[j-1],upperLeft))+1;
}
}
}
return dp[len2];
}
}