Day 26 of 30 days Leetcode Challenge - Longest Common Subsequence

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