FilesExpand file tree

 master

/

EditDistance.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

39 lines (37 loc) · 1.15 KB

 master

/

EditDistance.java

Top

File metadata and controls

• Code
• Blame

39 lines (37 loc) · 1.15 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

/**

* Given two words word1 and word2, find the minimum number of steps required to

* convert word1 to word2. (each operation is counted as 1 step.)

*

* You have the following 3 operations permitted on a word:

*

* a) Insert a character

* b) Delete a character

* c) Replace a character

*/

public class EditDistance {

public int minDistance(String word1, String word2) {

if (word1.length() == 0 || word2.length() == 0)

return word1.length() == 0 ? word2.length() : word1.length();

int[][] arr = new int[word2.length() + 1][word1.length() + 1];

for (int i = 0; i <= word1.length(); i++) {

arr[0][i] = i;

}

for (int j = 0; j <= word2.length(); j++) {

arr[j][0] = j;

}

for (int i = 0; i < word1.length(); i++) {

for (int j = 0; j < word2.length(); j++) {

if (word1.charAt(i) == word2.charAt(j)) {

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

} else {

int dis = Math.min(arr[j][i + 1], arr[j + 1][i]);

arr[j + 1][i + 1] = Math.min(arr[j][i], dis) + 1;

}

}

}

return arr[word2.length()][word1.length()];

}

public static void main (String[] args) {

System.out.println(new EditDistance().minDistance("ab", "bc"));

}

}