六刷 06/2022
Version #1 DP with optimized space
Time O(MN)
Space O(M)
Runtime: 12 ms, faster than 20.68% of Java online submissions for Edit Distance.
Memory Usage: 44 MB, less than 80.55% of Java online submissions for Edit Distance.
class Solution {
public int minDistance(String word1, String word2) {
int[][] dp = new int[2][word2.length() + 1];
for (int i = 0; i <= word1.length(); i++) {
for (int j = 0; j <= word2.length(); j++) {
if (i == 0 || j == 0) {
dp[i % 2][j] = i + j; // delete all characters
continue;
}
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i % 2][j] = dp[(i - 1) % 2][j - 1];
} else {
int min = Math.min(dp[(i - 1) % 2][j - 1], Math.min(dp[(i - 1) % 2][j], dp[i % 2][j - 1]));
dp[i % 2][j] = min + 1;
}
}
}
return dp[word1.length() % 2][word2.length()];
}
}
18.16 %
class Solution {
public int minDistance(String word1, String word2) {
if (word1 == null && word2 == null) return 0;
if (word1 == null || word1.length() == 0) return word2.length();
if (word2 == null || word2.length() == 0) return word1.length();
int[][] dp = new int[word1.length() + 1][word2.length() + 1];
// "" h o r s e
//"" 0 1 2 3 4 5
//r 1 2 3 2 3 4
//o 2
//s 3
for (int i = 0; i <= word1.length(); i++) {
for (int j = 0; j <= word2.length(); j++) {
if (i == 0) {
dp[i][j] = j;
} else if (j == 0) {
dp[i][j] = i;
} else {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
}
}
}
}
return dp[word1.length()][word2.length()];
}
}
四刷
74.19 %
class Solution {
public int minDistance(String word1, String word2) {
if (word1 == null && word2 == null) return 0;
if (word1 == null) return word2.length();
if (word2 == null) return word1.length();
int[] dp = new int[word2.length() + 1];
int prev = 0;
int curr = 0;
// prev -> dp[p1 - 1][p2 - 1]
for (int p1 = 0; p1 <= word1.length(); p1++) {
prev = dp[0];
dp[0] = p1;
for (int p2 = 1; p2 <= word2.length(); p2++) {
if (p1 == 0) {
curr = p2;
} else {
if (word1.charAt(p1 - 1) == word2.charAt(p2 - 1)) {
curr = prev;
} else {
curr = 1 + Math.min(prev, Math.min(dp[p2 - 1], dp[p2]));
}
}
prev = dp[p2];
dp[p2] = curr;
}
}
return dp[word2.length()];
}
}
三刷
和Version#2 类似，区别在于每次用一个新的array来记录当前一行的dp
然后替换prev
40.38 %
class Solution {
public int minDistance(String word1, String word2) {
// dp[i][j] -> match word1 [0, i) to word2 [0, j)
if (word1 == null && word2 == null) {
return 0;
}
if (word1 == null) {
return word2.length();
}
if (word2 == null) {
return word1.length();
}
int[] prev = null;
for (int i = 0; i <= word1.length(); i++) {
int[] curr = new int[word2.length() + 1];
curr[0] = i;
for (int j = 1; j <= word2.length(); j++) {
if (i == 0) {
curr[j] = j;
continue;
}
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
curr[j] = prev[j - 1];
} else {
curr[j] = 1 + Math.min(prev[j - 1], Math.min(prev[j], curr[j - 1]));
}
}
prev = curr;
}
return prev[word2.length()];
}
}
2ND TRY
Version #2 Optimized DP
Time O(mn) Space O(n)
99.73 %
class Solution {
public int minDistance(String word1, String word2) {
if (word1 == null && word2 == null) {
return 0;
}
if (word1 == null) {
return word2.length();
}
if (word2 == null) {
return word1.length();
}
int[] dp = new int[word2.length() + 1];
int prev = 0;
int curr = 0;
// prev -> dp[p1 - 1][p2 - 1]
for (int p1 = 0; p1 <= word1.length(); p1++) {
for (int p2 = 0; p2 <= word2.length(); p2++) {
if (p1 == 0) {
curr = p2;
} else if (p2 == 0) {
curr = p1;
} else {
if (word1.charAt(p1 - 1) == word2.charAt(p2 - 1)) {
curr = prev;
} else {
curr = 1 + Math.min(prev, Math.min(dp[p2 - 1], dp[p2]));
}
}
prev = dp[p2];
dp[p2] = curr;
}
}
return dp[word2.length()];
}
}
Version #1 Naive DP
Time O(mn) Space O(mn)
State transfer function has some issue
When char1 == char2 -> dp[p1][p2] = dp[p1 - 1][p2 - 1]
Else either replace or delete or add
93.68 %
class Solution {
public int minDistance(String word1, String word2) {
if (word1 == null || word2 == null) {
return 0;
}
// dp[p1][p2] -> min distance from word1 [0, p1) to word2 [0, p2)
// p1 p2
// " h o r s e " " r o s "
int[][] dp = new int[word1.length() + 1][word2.length() + 1];
for(int p1 = 0; p1 <= word1.length(); p1++) {
for (int p2 = 0; p2 <= word2.length(); p2++) {
if (p1 == 0) {
dp[p1][p2] = p2;
} else if (p2 == 0) {
dp[p1][p2] = p1;
} else {
if (word1.charAt(p1 - 1) == word2.charAt(p2 - 1)) {
dp[p1][p2] = dp[p1 - 1][p2 - 1];
} else {
dp[p1][p2] = 1 + Math.min(dp[p1 - 1][p2 - 1], Math.min(dp[p1 - 1][p2], dp[p1][p2 - 1]));
}
}
}
}
return dp[word1.length()][word2.length()];
}
}
1ST TRY
虽然写出来了但是还是不懂
看这个解释
66.02 %
http://www.dreamxu.com/books/dsa/dp/edit-distance.html
public class Solution {
public int minDistance(String word1, String word2) {
if (word1 == null || word2 == null) throw new IllegalArgumentException();
if (word1.length() == 0) return word2.length();
if (word2.length() == 0) return word1.length();
int l1 = word1.length();
int l2 = word2.length();
int[][] dp = new int[word1.length() + 1][word2.length() + 1];
//dp[i1][i2]-> the edit distance for word1.substring[0, i1] 0<=i1<l1
//word2.substring[0, i2] 0<=i2<l2
//When i2 == 0 just delete i1 characters from word1
for (int i1 = 0; i1 <= l1; i1++) {
dp[i1][0] = i1;
}
//When i1 == 0 just insert i2 characters into word1
for (int i2 = 0; i2 <= l2; i2++) {
dp[0][i2] = i2;
}
for (int i1 = 1; i1 <= l1; i1++) {
for (int i2 = 1; i2 <= l2; i2++) {
if (word1.charAt(i1 - 1) == word2.charAt(i2 - 1)) {
dp[i1][i2] = dp[i1 - 1][i2 - 1];
} else {
//dp[i1 - 1][i2] + 1 -> dp[i1][i2] delete i1 from word1
//dp[i1][i2 - 1] + 1 -> dp[i1][i2] insert i2 into word1
//dp[i1 - 1][i2 - 1] + 1 -> dp[i1][i2] replace i1 by i2
dp[i1][i2] = 1 + Math.min(Math.min(dp[i1 - 1][i2], dp[i1][i2 - 1]), dp[i1 - 1][i2 - 1]);
}
}
}
return dp[l1][l2];
}
}
No comments:
Post a Comment