Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 209
Good morning! Here's your coding interview problem for today.

This problem was asked by YouTube.

Write a program that computes the length of the longest common subsequence of three given strings. For example, given "epidemiologist", "refrigeration", and "supercalifragilisticexpialodocious", it should return 5, since the longest common subsequence is "eieio".

Pull request:
Day209
Resolves #431.

Patch:
diff --git a/README.md b/README.md
index e490863..ff4e2f2 100644
--- a/README.md
+++ b/README.md
@@ -219,6 +219,7 @@ problems from
 * [Day 206](https://github.com/vaskoz/dailycodingproblem-go/issues/424)
 * [Day 207](https://github.com/vaskoz/dailycodingproblem-go/issues/426)
 * [Day 208](https://github.com/vaskoz/dailycodingproblem-go/issues/427)
+* [Day 209](https://github.com/vaskoz/dailycodingproblem-go/issues/431)
 * [Day 210](https://github.com/vaskoz/dailycodingproblem-go/issues/432)
 * [Day 211](https://github.com/vaskoz/dailycodingproblem-go/issues/434)
 * [Day 212](https://github.com/vaskoz/dailycodingproblem-go/issues/436)
diff --git a/day209/problem.go b/day209/problem.go
new file mode 100644
index 0000000..aeee9fc
--- /dev/null
+++ b/day209/problem.go
@@ -0,0 +1,75 @@
+package day209
+
+// LengthLongestCommonSubseqOf3Iterative is the iterative version.
+func LengthLongestCommonSubseqOf3Iterative(one, two, three string) int {
+	X := []rune(one)
+	Y := []rune(two)
+	Z := []rune(three)
+	dp := make([][][]int, len(X)+1)
+	for i := range dp {
+		dp[i] = make([][]int, len(Y)+1)
+		for j := range dp[i] {
+			dp[i][j] = make([]int, len(Z)+1)
+			for k := range dp[i][j] {
+				if i == 0 || j == 0 || k == 0 {
+					dp[i][j][k] = 0
+				} else if X[i-1] == Y[j-1] && X[i-1] == Z[k-1] {
+					dp[i][j][k] = 1 + dp[i-1][j-1][k-1]
+				} else {
+					dp[i][j][k] = max(
+						max(
+							dp[i-1][j][k],
+							dp[i][j-1][k],
+						),
+						dp[i][j][k-1],
+					)
+				}
+			}
+		}
+	}
+	return dp[len(X)][len(Y)][len(Z)]
+}
+
+// LengthLongestCommonSubseqOf3Recursive is the recursive version.
+func LengthLongestCommonSubseqOf3Recursive(one, two, three string) int {
+	dp := make([][][]int, len(one)+1)
+	for i := range dp {
+		dp[i] = make([][]int, len(two)+1)
+		for j := range dp[i] {
+			dp[i][j] = make([]int, len(three)+1)
+			for k := range dp[i][j] {
+				dp[i][j][k] = -1
+			}
+		}
+	}
+	return lengthLongestCommonSubseqOf3(dp, []rune(one), []rune(two), []rune(three))
+}
+
+func lengthLongestCommonSubseqOf3(dp [][][]int, one, two, three []rune) int {
+	i, j, k := len(one)-1, len(two)-1, len(three)-1
+	if i < 0 || j < 0 || k < 0 {
+		return 0
+	}
+	if dp[i][j][k] != -1 {
+		return dp[i][j][k]
+	}
+	if one[i] == two[j] && two[j] == three[k] {
+		dp[i][j][k] = 1 + lengthLongestCommonSubseqOf3(dp, one[:i], two[:j], three[:k])
+		return dp[i][j][k]
+	}
+	dp[i][j][k] = max(
+		max(
+			lengthLongestCommonSubseqOf3(dp, one[:i], two, three),
+			lengthLongestCommonSubseqOf3(dp, one, two[:j], three),
+		),
+		lengthLongestCommonSubseqOf3(dp, one, two, three[:k]),
+	)
+	return dp[i][j][k]
+}
+
+func max(a, b int) int {
+	if a > b {
+		return a
+	}
+	return b
+}


Test patch:
diff --git a/day209/problem_test.go b/day209/problem_test.go
new file mode 100644
index 0000000..1de0e16
--- /dev/null
+++ b/day209/problem_test.go
@@ -0,0 +1,45 @@
+package day209
+
+import "testing"
+
+var testcases = []struct {
+	one, two, three string
+	longest         int
+}{
+	{"epidemiologist", "refrigeration", "supercalifragilisticexpialodocious", 5},
+	{"epidemiologist", "supercalifragilisticexpialodocious", "refrigeration", 5},
+}
+
+func TestLengthLongestCommonSubseqOf3Recursive(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := LengthLongestCommonSubseqOf3Recursive(tc.one, tc.two, tc.three); tc.longest != result {
+			t.Errorf("Expected %v, got %v", tc.longest, result)
+		}
+	}
+}
+
+func BenchmarkLengthLongestCommonSubseqOf3Recursive(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			LengthLongestCommonSubseqOf3Recursive(tc.one, tc.two, tc.three)
+		}
+	}
+}
+
+func TestLengthLongestCommonSubseqOf3Iterative(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := LengthLongestCommonSubseqOf3Iterative(tc.one, tc.two, tc.three); tc.longest != result {
+			t.Errorf("Expected %v, got %v", tc.longest, result)
+		}
+	}
+}
+
+func BenchmarkLengthLongestCommonSubseqOf3Iterative(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			LengthLongestCommonSubseqOf3Iterative(tc.one, tc.two, tc.three)
+		}
+	}
+}