## 1143. Longest Common Subsequence

Updated on with 0 views and 0 comments

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

A 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"`.

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

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.

golang:

``````func longestCommonSubsequence(text1 string, text2 string) int {
var size1 = len(text1)
var size2 = len(text2)

var dp = make([][]int, size1 + 1)
for i := range dp {
dp[i] = make([]int, size2 + 1)
}

// 初始条件都是0
var maxSize = 0

for i := 0; i < size1; i++ {
for j := 0; j < size2; j++ {
// 因为定义的时候都保证比字符串大一位，这里直接够存就行。
if text1[i] == text2[j] {
dp[i+1][j+1] = dp[i][j] + 1
} else {
dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
}

// 更新最大值
maxSize = max(dp[i+1][j+1], maxSize)
}
}

return maxSize
}

func max(i, j int) int {
if i < j {
return j
}
return i
}
``````