FilesExpand file tree

 master

/

EditDistance.js

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

54 lines (43 loc) · 1.31 KB

 master

/

EditDistance.js

Top

File metadata and controls

• Code
• Blame

54 lines (43 loc) · 1.31 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

/*

Wikipedia -> https://en.wikipedia.org/wiki/Edit_distance

Q. -> Given two strings `word1` and `word2`. You can perform these operations on any of the string to make both strings similar.

- Insert

- Remove

- Replace

Find the minimum operation cost required to make both same. Each operation cost is 1.

Algorithm details ->

time complexity - O(n*m)

space complexity - O(n*m)

*/

const minimumEditDistance = (word1, word2) => {

const n = word1.length

const m = word2.length

const dp = new Array(m + 1).fill(0).map(item => [])

/*

fill dp matrix with default values -

- first row is filled considering no elements in word2.

- first column filled considering no elements in word1.

*/

for (let i = 0; i < n + 1; i++) {

dp[0][i] = i

}

for (let i = 0; i < m + 1; i++) {

dp[i][0] = i

}

/*

indexing is 1 based for dp matrix as we defined some known values at first row and first column/

*/

for (let i = 1; i < m + 1; i++) {

for (let j = 1; j < n + 1; j++) {

const letter1 = word1[j - 1]

const letter2 = word2[i - 1]

if (letter1 === letter2) {

dp[i][j] = dp[i - 1][j - 1]

} else {

dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]) + 1

}

}

}

return dp[m][n]

}

export { minimumEditDistance }