From cb80b1dcdb3c4822464e64a10768d21d473e3b78 Mon Sep 17 00:00:00 2001 From: terminaldweller Date: Thu, 15 Dec 2022 14:02:15 +0330 Subject: 1143 --- 1143/go.mod | 3 +++ 1143/main.go | 38 ++++++++++++++++++++++++++++++++++++++ 2 files changed, 41 insertions(+) create mode 100644 1143/go.mod create mode 100644 1143/main.go diff --git a/1143/go.mod b/1143/go.mod new file mode 100644 index 0000000..b30ffef --- /dev/null +++ b/1143/go.mod @@ -0,0 +1,3 @@ +module 1143 + +go 1.19 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")) +} -- cgit v1.2.3