-
Notifications
You must be signed in to change notification settings - Fork 0
/
edit_distance.jav
33 lines (32 loc) · 954 Bytes
/
edit_distance.jav
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
//finding minimum no of operations(insert,delete or replace operations) to convert one string to other through dynamic programming
class Solution {
public int editDistance(String s, String t) {
int[][] a=new int[s.length()+1][t.length()+1];
for(int k=0;k<=s.length();k++)
{
for(int m=0;m<=t.length();m++)
{
if(k==0)
{
a[k][m]=m;
}
else if(m==0)
{
a[k][m]=k;
}
else
{
if(s.charAt(k-1)==t.charAt(m-1))
{
a[k][m]=a[k-1][m-1];
}
else
{
a[k][m]=1+Math.min(Math.min(a[k][m-1],a[k-1][m]),a[k-1][m-1]);
}
}
}
}
return a[s.length()][t.length()];
}
}