Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 31
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

The edit distance between two strings refers to the minimum number of character insertions, deletions, and substitutions required to change one string to the other. For example, the edit distance between “kitten” and “sitting” is three: substitute the “k” for “s”, substitute the “e” for “i”, and append a “g”.

Given two strings, compute the edit distance between them.

Pull request:
Day31
Resolves #71 

Patch:
diff --git a/README.md b/README.md
index f215268..aaa13ee 100644
--- a/README.md
+++ b/README.md
@@ -44,4 +44,5 @@ problems from
 * [Day 28](https://github.com/vaskoz/dailycodingproblem-go/issues/65)
 * [Day 29](https://github.com/vaskoz/dailycodingproblem-go/issues/67)
 * [Day 30](https://github.com/vaskoz/dailycodingproblem-go/issues/69)
+* [Day 31](https://github.com/vaskoz/dailycodingproblem-go/issues/71)
 * [Day 33](https://github.com/vaskoz/dailycodingproblem-go/issues/73)
diff --git a/day31/problem.go b/day31/problem.go
new file mode 100644
index 0000000..ff2ec8f
--- /dev/null
+++ b/day31/problem.go
@@ -0,0 +1,38 @@
+package day31
+
+// EditDistance returns the minimum number of additions, removals,
+// and substitutions required to make the two strings equal.
+// Runtime O(len(s)*len(t)) and space O(len(s)*len(t))
+func EditDistance(s, t string) int {
+	d := make([][]int, len(s)+1)
+	for i := range d {
+		d[i] = make([]int, len(t)+1)
+		d[i][0] = i
+	}
+	for j := range d[0] {
+		d[0][j] = j
+	}
+	for j, tr := range t {
+		for i, sr := range s {
+			if sr == tr {
+				d[i+1][j+1] = d[i][j]
+			} else {
+				d[i+1][j+1] = minimum(d[i][j+1]+1,
+					d[i+1][j]+1,
+					d[i][j]+1)
+			}
+		}
+	}
+	return d[len(s)][len(t)]
+}
+
+func minimum(a, b, c int) int {
+	result := a
+	if b < result {
+		result = b
+	}
+	if c < result {
+		result = c
+	}
+	return result
+}


Test patch:
diff --git a/day31/problem_test.go b/day31/problem_test.go
new file mode 100644
index 0000000..eb9dafa
--- /dev/null
+++ b/day31/problem_test.go
@@ -0,0 +1,27 @@
+package day31
+
+import "testing"
+
+var testcases = []struct {
+	s1, s2 string
+	diff   int
+}{
+	{"kitten", "sitting", 3},
+}
+
+func TestEditDistance(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if diff := EditDistance(tc.s1, tc.s2); diff != tc.diff {
+			t.Errorf("Expected %v got %v", tc.diff, diff)
+		}
+	}
+}
+
+func BenchmarkEditDistance(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			EditDistance(tc.s1, tc.s2)
+		}
+	}
+}