# golang_longest_common_subsequence

Given two strings `text1` and `text2`, return the length of their longest common subsequence. If there is no common subsequence, return `0`.

subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, `"ace"` is a subsequence of `"abcde"`.

common subsequence of two strings is a subsequence that is common to both strings.

## Examples

Example 1:

``````Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.

``````

Example 2:

``````Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

``````

Example 3:

``````Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

``````

Constraints:

• `1 <= text1.length, text2.length <= 1000`
• `text1` and `text2` consist of only lowercase English characters.

## 解析

len(common_substring) ≤ min(len(text1), len(text2)) d[i][j] = d[i+1][j+1]+1 , if text1[i] == text2[j]

d[i][j] = max(d[i+1][j], d[i][j+1]) if text1[i] ≠ text2[j] ## 程式碼

```package sol

func longestCommonSubsequence(text1 string, text2 string) int {
m, n := len(text1), len(text2)
dp := make([][]int, m+1)
for row := range dp {
dp[row] = make([]int, n+1)
}
var max = func(a, b int) int {
if a > b {
return a
}
return b
}
// start from last Idx reduce the repetition
// dp[i][j] = dp[i+1][j+1] if text1[i] == text2[j]
// dp[i][j] = max(dp[i+1][j], dp[i][j+1]) if text1[i] != text2[j]
for text1_start := m - 1; text1_start >= 0; text1_start-- {
for text2_start := n - 1; text2_start >= 0; text2_start-- {
if text1[text1_start] == text2[text2_start] {
dp[text1_start][text2_start] = dp[text1_start+1][text2_start+1] + 1
} else {
dp[text1_start][text2_start] = max(
dp[text1_start+1][text2_start],
dp[text1_start][text2_start+1],
)
}
}
}
return dp
}```

## 困難點

1. 要能找出最長子字串的遞迴子關係

## Solve Point

• 建立一個 m+1 by n+1 的整數矩陣 dp 用來儲存動態規劃的中間計算結果
• 透過 dp[i][j] 的遞迴關係式從 i = m+1, j = n+1 逐步往前推算
• 回傳 dp

View Github