GeezerVison is showing github.com — Java/DynamicProgramming/EditDistance.java at master · kaishui/Java

Expand file tree

EditDistance.java

Copy path

More file actions

Latest commit

History

118 lines (105 loc) · 3.77 KB

EditDistance.java

Copy path

File metadata and controls

118 lines (105 loc) · 3.77 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

package DynamicProgramming;

/**

* A DynamicProgramming based solution for Edit Distance problem In Java Description of Edit

* Distance with an Example:

* <p>Edit distance is a way of quantifying how dissimilar two strings (e.g., words) are to one

* another, by counting the minimum number of operations required to transform one string into the

* other. The distance operations are the removal, insertion, or substitution of a character in the

* string.

* <p>

* <p>The Distance between "kitten" and "sitting" is 3. A minimal edit script that transforms the

* former into the latter is:

* <p>kitten → sitten (substitution of "s" for "k") sitten → sittin (substitution of "i" for "e")

* sittin → sitting (insertion of "g" at the end).

* @author SUBHAM SANGHAI

import java.util.Scanner;

public class EditDistance {

public static int minDistance(String word1, String word2) {

int len1 = word1.length();

int len2 = word2.length();

// len1+1, len2+1, because finally return dp[len1][len2]

int[][] dp = new int[len1 + 1][len2 + 1];

/* If second string is empty, the only option is to

insert all characters of first string into second*/

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

dp[i][0] = i;

}

/* If first string is empty, the only option is to

insert all characters of second string into first*/

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

dp[0][j] = j;

}

// iterate though, and check last char

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

char c1 = word1.charAt(i);

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

char c2 = word2.charAt(j);

// if last two chars equal

if (c1 == c2) {

// update dp value for +1 length

dp[i + 1][j + 1] = dp[i][j];

} else {

/* if two characters are different ,

then take the minimum of the various operations(i.e insertion,removal,substitution)*/

int replace = dp[i][j] + 1;

int insert = dp[i][j + 1] + 1;

int delete = dp[i + 1][j] + 1;

int min = replace > insert ? insert : replace;

min = delete > min ? min : delete;

dp[i + 1][j + 1] = min;

}

/* return the final answer , after traversing through both the strings*/

return dp[len1][len2];

}

public static void main(String[] args) {

Scanner input = new Scanner(System.in);

String s1, s2;

System.out.println("Enter the First String");

s1 = input.nextLine();

System.out.println("Enter the Second String");

s2 = input.nextLine();

// ans stores the final Edit Distance between the two strings

int ans = minDistance(s1, s2);

System.out.println(

"The minimum Edit Distance between \"" + s1 + "\" and \"" + s2 + "\" is " + ans);

input.close();

}

// edit distance problem

public static int editDistance(String s1, String s2){

int[][] storage = new int[s1.length() + 1][s2.length() + 1];

return editDistance(s1, s2,storage);

}

public static int editDistance(String s1, String s2, int[][] storage) {

int m = s1.length();

int n = s2.length();

if (storage[m][n] > 0) {

return storage[m][n];

}

if (m== 0) {

storage[m][n] = n;

return storage[m][n];

}

if (n== 0) {

storage[m][n] = m;

return storage[m][n];

}

if (s1.charAt(0) == s2.charAt(0)) {

storage[m][n] = editDistance(s1.substring(1), s2.substring(1), storage);

return storage[m][n];

} else {

int op1 = editDistance(s1, s2.substring(1),storage);

int op2 = editDistance(s1.substring(1), s2,storage);

int op3 = editDistance(s1.substring(1),s2.substring(1),storage);

storage[m][n] = 1 + Math.min(op1, Math.min(op2, op3));

return storage[m][n];

}