1143

1 files changed, 38 insertions, 0 deletions

diff --git a/1143/main.go b/1143/main.go
new file mode 100644
index 0000000..20b1bc0
--- /dev/null
+++ b/1143/main.go
@@ -0,0 +1,38 @@
+package main
+
+import "fmt"
+
+func max(a, b int) int {
+	if a > b {
+		return a
+	}
+	return b
+}
+
+func longestCommonSubsequence(text1 string, text2 string) int {
+	l1 := len(text1)
+	l2 := len(text2)
+	dp := make([][]int, l1+1)
+	for i := range dp {
+		dp[i] = make([]int, l2+1)
+	}
+
+	for i := 0; i < l1; i++ {
+		for j := 0; j < l2; j++ {
+			if text1[i] == text2[j] {
+				dp[i+1][j+1] = dp[i][j] + 1
+			} else {
+				dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
+			}
+		}
+	}
+
+	return dp[l1][l2]
+}
+
+func main() {
+	fmt.Println(longestCommonSubsequence("abcde", "ace"))
+	fmt.Println(longestCommonSubsequence("abc", "abc"))
+	fmt.Println(longestCommonSubsequence("abc", "def"))
+	fmt.Println(longestCommonSubsequence("aced", "aceaced"))
+}