FilesExpand file tree

 master

/

LevenshteinDistance.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

55 lines (47 loc) · 1.28 KB

 master

/

LevenshteinDistance.java

Copy path

Top

File metadata and controls

• Code
• Blame

55 lines (47 loc) · 1.28 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

/**

*

* @author Kshitij VERMA (github.com/kv19971)

* LEVENSHTEIN DISTANCE dyamic programming implementation to show the difference between two strings (https://en.wikipedia.org/wiki/Levenshtein_distance)

*

*

*/

public class LevenshteinDistance{

private static int minimum(int a, int b, int c){

if(a < b && a < c){

return a;

}else if(b < a && b < c){

return b;

}else{

return c;

}

}

private static int calculate_distance(String a, String b){

int len_a = a.length() + 1;

int len_b = b.length() + 1;

int [][] distance_mat = new int[len_a][len_b];

for(int i = 0; i < len_a; i++){

distance_mat[i][0] = i;

}

for(int j = 0; j < len_b; j++){

distance_mat[0][j] = j;

}

for(int i = 0; i < len_a; i++){

for(int j = 0; i < len_b; j++){

int cost;

if (a.charAt(i) == b.charAt(j)){

cost = 0;

}else{

cost = 1;

}

distance_mat[i][j] = minimum(distance_mat[i-1][j], distance_mat[i-1][j-1], distance_mat[i][j-1]) + cost;

}

}

return distance_mat[len_a-1][len_b-1];

}

public static void main(String [] args){

String a = ""; // enter your string here

String b = ""; // enter your string here

System.out.print("Levenshtein distance between "+a + " and "+b+ " is: ");

System.out.println(calculate_distance(a,b));

}

}