Movatterモバイル変換

[0]ホーム
URL:

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

 Sign up
Appearance settings

Commit0aee19d

Browse files
Merge pull requestTheAlgorithms#101 from kv19971/levenshtein_distance
added levenshtein distance dp implementation
2 parents995005c +0957f33 commit0aee19d

File tree

1 file changed

+55
-0
lines changed

1 file changed

+55
-0
lines changed
Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
/**
2+
*
3+
* @author Kshitij VERMA (github.com/kv19971)
4+
* LEVENSHTEIN DISTANCE dyamic programming implementation to show the difference between two strings (https://en.wikipedia.org/wiki/Levenshtein_distance)
5+
*
6+
*
7+
*/
8+
9+
publicclassLevenshtein_distance{
10+
privateintminimum(inta,intb,intc){
11+
if(a <b &&a <c){
12+
returna;
13+
}elseif(b <a &&b <c){
14+
returnb;
15+
}else{
16+
returnc;
17+
}
18+
}
19+
publicintcalculate_distance(Stringa,Stringb){
20+
len_a =a.length() +1;
21+
len_b =b.length() +1;
22+
int [][]distance_mat =newint[len_a][len_b];
23+
for(inti =0;i <len_a;i++){
24+
distance_mat[i][0] =i;
25+
}
26+
for(intj =0;j <len_b;j++){
27+
distance_mat[0][j] =j;
28+
}
29+
for(inti =0;i <len_a;i++){
30+
for(intj =0;i <len_b;j++){
31+
intcost;
32+
if (a.charAt(i) ==b.charAt(j)){
33+
cost =0;
34+
}else{
35+
cost =1;
36+
}
37+
distance_mat[i][j] =minimum(distance_mat[i-1][j],distance_mat[i-1][j-1],distance_mat[i][j-1]) +cost;
38+
39+
40+
}
41+
42+
}
43+
returndistance_mat[len_a-1][len_b-1];
44+
45+
}
46+
publicstaticvoidmain(String []args){
47+
Stringa ="";// enter your string here
48+
Stringb ="";// enter your string here
49+
50+
System.out.print("Levenshtein distance between "+a +" and "+b+" is: ");
51+
System.out.println(calculate_distance(a,b));
52+
53+
54+
}
55+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp