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”, while “aec” is not. A common subsequence 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 equal, add 1 and move both strings backward; otherwise take the max of moving the first string backward or moving the second string backward.
2. Approach 2
   • Dynamic programming

3. Implementation

3.1. Recursion

// 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. 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