Longest Common Subsequence

1. Problem Description

Given two strings text1 and text2, return the length of their longest common subsequence.

A subsequence of a string is a new string formed from the original string by deleting some characters (possibly none) without changing the relative order of the remaining characters. For example, “ace” is a subsequence of “abcde”, but “aec” is not. A common subsequence of two strings is a subsequence shared by both strings.

If the two strings have no common subsequence, return 0.

2. Approach

1. Approach 1
   • Recursion
   • Start matching from the last character. If they are the same, add 1 and move both backward; otherwise take max (move the first backward, or move the second backward)
2. Approach 2
   • Dynamic programming

3. Implementation

3.1. DFS

// Time: O(2^N)
func longestCommonSubsequence(text1 string, text2 string) int {
	if text1 == "" || text2 == "" {
		return 0
	}

	if text1[len(text1)-1] == text2[len(text2)-1] {
		return 1 + longestCommonSubsequence(text1[:len(text1)-1], text2[:len(text2)-1])
	}

	return max(longestCommonSubsequence(text1[:len(text1)-1], text2),
		longestCommonSubsequence(text1, text2[:len(text2)-1]))
}

func max(data ...int) int {
	max := data[0]
	for i := 1; i < len(data); i++ {
		if data[i] > max {
			max = data[i]
		}
	}
	return max
}

3.2. DFS + Memoization

func longestCommonSubsequence(text1 string, text2 string) int {
    memo := make(map[string]int, 0)
    return longestCommonSubsequenceDFS(text1, text2, 0, 0, memo)
}

func longestCommonSubsequenceDFS(text1, text2 string, index1, index2 int, memo map[string]int) int {
    if index1 >= len(text1) || index2 >= len(text2) {return 0}
    key := buildKey(index1, index2)
    count, ok := memo[key]
    if ok {
        return count
    }
    if text1[index1] == text2[index2] {
        count = 1 + longestCommonSubsequenceDFS(text1, text2, index1+1, index2+1, memo)
    } else {
        count = max(longestCommonSubsequenceDFS(text1, text2, index1+1, index2, memo),
            longestCommonSubsequenceDFS(text1, text2, index1, index2+1, memo))
    }
    memo[key] = count
    return count
}

func max(a, b int) int {
    if a > b {return a}
    return b
}

func buildKey(index1, index2 int) string {
    return fmt.Sprintf("%v_%v", index1, index2)
}

3.3. Dynamic Programming

func max(data ...int) int {
	max := data[0]
	for i := 1; i < len(data); i++ {
		if data[i] > max {
			max = data[i]
		}
	}
	return max
}

// Time: O(m*n)
func longestCommonSubsequence2(text1 string, text2 string) int {
	dp := make([][]int, len(text1)+1, len(text1)+1)
	for i := 0; i <= len(text1); i++ {
		dp[i] = make([]int, len(text2)+1, len(text2)+1)
	}

	for i := 1; i <= len(text1); i++ {
		for j := 1; j <= len(text2); j++ {
			if text1[i-1] == text2[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])
			}
		}
	}
	return dp[len(text1)][len(text2)]
}

4. References

• 1143. Longest Common Subsequence - LeetCode