HàPhan 河

Longest Common Subsequence

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]
}

}

``````