Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Expand file tree

/

Edit Distance.java

Copy path
More file actions
More file actions

Latest commit

 

History

History
History
executable file
·
62 lines (48 loc) · 1.75 KB
/

Edit Distance.java

Copy path

File metadata and controls

executable file
·
62 lines (48 loc) · 1.75 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
M
Not Done
```
/*
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:
Insert a character
Delete a character
Replace a character
Example
Given word1 = "mart" and word2 = "karma", return 3.
Tags Expand
String Dynamic Programming
Thoughts:
Draw a 2D array, consider rows as word1 and cols as word2.
DP[i][j] means the steps (edit distance) to take to transfer word1[0 ~ i] to word2[0 ~ j]
And, we have 3 different calculations for the 3 methods:
1. Replace: DP[i][j] = word1[i-1] == word2[j-1] ? DP[i - 1][j - 1] : DP[i-1][j-1] + 1;
2. Insert: DP[i][j] = word1[i - 1][j] + 1; // missing 1 char in word1
3. Delete: DP[i][j] = word1[i][j - 1] + 1; // extra char in word1
Note: just remember to start from i=1,j=1, because we are using DP[i-1][j-1], becareful with border case
*/
public class Solution {
public int minDistance(String word1, String word2) {
if (word1 == null && word2 != null) {
return word2.length();
} else if (word1 != null && word2 == null) {
return word1.length();
} else if (word1 == null && word2 == null) {
return 0;
}
int[][] DP = new int[word1.length() + 1][word2.length() + 1];
for (int i = 1; i <= word1.length(); i++) {
DP[i][0] = i;
}
for (int j = 1; j <= word2.length(); j++) {
DP[0][j] = j;
}
for (int i = 1; i <= word1.length(); i++) {
for (int j = 1; j <= word2.length(); j++) {
DP[i][j] = Math.min(Math.min(DP[i - 1][j] + 1, DP[i][j - 1] + 1), word1.charAt(i - 1) == word2.charAt(j - 1) ? DP[i - 1][j - 1] : DP[i - 1][j - 1] + 1);
}
}
return DP[word1.length()][word2.length()];
}
}
```
Morty Proxy This is a proxified and sanitized view of the page, visit original site.