FilesExpand file tree

master

/

editdistance.go

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

71 lines (55 loc) · 2.04 KB

master

/

editdistance.go

Copy path

Top

File metadata and controls

• Code
• Blame

71 lines (55 loc) · 2.04 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

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

// EDIT DISTANCE PROBLEM

// time complexity: O(m * n) where m and n are lengths of the strings, first and second respectively.

// space complexity: O(m * n) where m and n are lengths of the strings, first and second respectively.

// https://www.geeksforgeeks.org/edit-distance-dp-5/

// https://leetcode.com/problems/edit-distance/

package dynamic

import "github.com/TheAlgorithms/Go/math/min"

// EditDistanceRecursive is a naive implementation with exponential time complexity.

func EditDistanceRecursive(first string, second string, pointerFirst int, pointerSecond int) int {

if pointerFirst == 0 {

return pointerSecond

}

if pointerSecond == 0 {

return pointerFirst

}

// Characters match, so we recur for the remaining portions

if first[pointerFirst-1] == second[pointerSecond-1] {

return EditDistanceRecursive(first, second, pointerFirst-1, pointerSecond-1)

}

// We have three choices, all with cost of 1 unit

return 1 + min.Int(EditDistanceRecursive(first, second, pointerFirst, pointerSecond-1), // Insert

EditDistanceRecursive(first, second, pointerFirst-1, pointerSecond), // Delete

EditDistanceRecursive(first, second, pointerFirst-1, pointerSecond-1)) // Replace

}

// EditDistanceDP is an optimised implementation which builds on the ideas of the recursive implementation.

// We use dynamic programming to compute the DP table where dp[i][j] denotes the edit distance value

// of first[0..i-1] and second[0..j-1]. Time complexity is O(m * n) where m and n are lengths of the strings,

// first and second respectively.

func EditDistanceDP(first string, second string) int {

m := len(first)

n := len(second)

// Create the DP table

dp := make([][]int, m+1)

for i := 0; i <= m; i++ {

dp[i] = make([]int, n+1)

}

for i := 0; i <= m; i++ {

for j := 0; j <= n; j++ {

if i == 0 {

dp[i][j] = j

continue

}

if j == 0 {

dp[i][j] = i

continue

}

if first[i-1] == second[j-1] {

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

continue

}

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

}

}

return dp[m][n]

}