Given two strings `text1`

and `text2`

, return the length of their longest common subsequence.

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. (eg, "ace" is a subsequence of "abcde" while "aec" is not). A *common subsequence* of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

**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 <= 1000`

`1 <= text2.length <= 1000`

- The input strings consist of lowercase English characters only.

**Solution**

It's popular dp problem.

```
1. when last character is different
LCS(0...n, 0...m) = max { LCS(0...n-1, 0...m), LCS(0...n, 0...m-1) }
2. when last character is same
LCS(0...n, 0...m) = 1 + LCS(0...n-1, 0...m-1)
3. LCS(n,m) will be resolved in some cases, so use dp to get rid of it.
```

**Recursive solution**

```
class Solution {
func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
if text1 == text2 {
return text1.count
}
var chars1 = Array(text1)
var chars2 = Array(text2)
var dp = Array(repeating: Array(repeating: -1, count: text2.count), count: text1.count)
return lcs(&chars1, &chars2, chars1.count, chars2.count, &dp)
}
func lcs(_ text1: inout [Character], _ text2: inout [Character], _ n: Int, _ m: Int, _ dp: inout [[Int]]) -> Int {
if n == 0 || m == 0 {
return 0
}
var result : Int = 0
if dp[n - 1][m - 1] != -1 {
result = dp[n - 1][m - 1]
}else if text1[n-1] == text2[m-1] {
result = 1 + lcs(&text1, &text2, n - 1, m - 1, &dp)
}else{
let lcs1 = lcs(&text1, &text2, n, m - 1, &dp)
let lcs2 = lcs(&text1, &text2, n - 1, m, &dp)
result = max(lcs1, lcs2)
}
dp[n-1][m-1] = result
return result
}
}
```

**Iterative Solution**

```
class Solution {
func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
if text1 == text2 {
return text1.count
}
var chars1 = Array(text1)
var chars2 = Array(text2)
var n = text1.count
var m = text2.count
var dp = Array(repeating: Array(repeating: 0, count: m + 1), count: n + 1)
for i in 0..<n {
for j in 0..<m {
if chars1[i] == chars2[j] {
dp[i+1][j+1] = 1 + dp[i][j]
}else{
dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
}
}
}
return dp[n][m]
}
}
```