-
Notifications
You must be signed in to change notification settings - Fork 3
/
EditDistance.java
83 lines (63 loc) · 2.01 KB
/
EditDistance.java
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// http://www.geeksforgeeks.org/dynamic-programming-set-5-edit-distance/
/*
Also called as Lavenshtein Distance
The Levenshtein distance, or edit distance, is the amount by which two strings differ.
Operations -
1. Insert (Addition)
2. Remove (Deletion)
3. Replace (Modification)
Algorithm -
// if either of the strings
// is empty
levd(i,j) = max(i,j)
// if the last character of
// both substrings match
// s1[i] == s2[j]
levd(i,j) = min(levd(i-1,j),
levd(i,j-1),
levd(i-1,j-1))
// in any other case
levd(i,j) = min(levd(i-1,j)+1,
levd(i,j-1)+1,
levd(i-1,j-1)+1)
Time Complexity - O(3^m) operations
The worst case happens when none of characters of two strings match.
Dynamic Programming - Use an auxillary array to store the computed values.
Overlapping Subproblems
- Memoization (Top Down approach)
- Tabulation (Bottom Up approach)
Optimal Substructure
Solved using Memoization method (Top Down approach)
Time Complexity: O(m x n)
Auxiliary Space: O(m x n)
*/
class EditDistance {
static int[][] arr;
public static int min( int x, int y, int z ) {
if ( x < y )
return x < z ? x : z;
else
return y < z ? y : z;
}
public static int editDist( String str1, String str2, int m, int n ) {
for(int i = 0; i <= m; i++) {
for(int j = 0; j <= n; j++) {
if(i==0)
arr[i][j] = j;
else if(j == 0)
arr[i][j] = i;
else if(str1.charAt(i-1) == str2.charAt(j-1))
arr[i][j] = arr[i-1][j-1];
else
arr[i][j] = 1 + min(arr[i-1][j], arr[i-1][j-1], arr[i][j-1]);
}
}
return arr[m][n];
}
public static void main(String[] args) {
String str1 = "sitting";
String str2 = "kitten";
arr = new int[str1.length() + 1][str2.length() + 1];
System.out.println( editDist( str1 , str2 , str1.length(), str2.length()) );
}
}