This repository was archived by the owner on Sep 7, 2025. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 83
Expand file tree
/
Copy pathEDIST.java
More file actions
46 lines (39 loc) · 1.54 KB
/
EDIST.java
File metadata and controls
46 lines (39 loc) · 1.54 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
// A Naive recursive Java program to find minimum number
// operations to convert str1 to str2
class EDIST
{
static int min(int x,int y,int z)
{
if (x<=y && x<=z) return x;
if (y<=x && y<=z) return y;
else return z;
}
static int editDist(String str1 , String str2 , int m ,int n)
{
// If first string is empty, the only option is to
// insert all characters of second string into first
if (m == 0) return n;
// If second string is empty, the only option is to
// remove all characters of first string
if (n == 0) return m;
// If last characters of two strings are same, nothing
// much to do. Ignore last characters and get count for
// remaining strings.
if (str1.charAt(m-1) == str2.charAt(n-1))
return editDist(str1, str2, m-1, n-1);
// If last characters are not same, consider all three
// operations on last character of first string, recursively
// compute minimum cost for all three operations and take
// minimum of three values.
return 1 + min ( editDist(str1, str2, m, n-1), // Insert
editDist(str1, str2, m-1, n), // Remove
editDist(str1, str2, m-1, n-1) // Replace
);
}
public static void main(String args[])
{
String str1 = "sunday";
String str2 = "saturday";
System.out.println( editDist( str1 , str2 , str1.length(), str2.length()) );
}
}