Daily LeetCode 1143. Longest Common Subsequence

https://leetcode.com/problems/longest-common-subsequence/submissions/

Medium

问题描述：

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.

题目分析：

这一题是要找出两个字符串之间的最长公共子串。

思路一：

分别找出两个字符串的子串，然后找出最长的公共子串即可，这种暴力解法在思路上很直接，但是求子串的过程会耗费大量的时间和空间，因此这种方法并不适合。

思路二：

这题其实是一道典型的用动态规划解决的题目，在解决两个字符串相关的问题时，通常需要维护一个二维数组，来描述两个字符串之间的关系。

我们初始化一个dp数组，dp[i][j]表示当前情况下最长的公共子串长度，即text1前i个元素与text2前j个元素能构成的最长公共子串长度（i，j不包括在内）。

接着我们来考虑状态转移方程，更新dp[i][j]时应当考虑两种情况：第一种是当前遍历的字符相等的情况，即text1[i]==text2[j]，此时，dp[i][j]=dp[i-1][j-1]+1，即text1前i-1个元素与text2前j-1个元素能构成的最长公共子串长度加1；第二种情况是当前遍历的字符不想等的情况，由于字符不等，因此我们只能在dp[i-1][j], dp[i][j-1]中选一个最大值，因为我们此时不能扩展公共子串了，此时，dp[i][j]=max(dp[i-1][j], dp[i][j-1])。

以Example1为例：

current text1 index: 1, current text2 index: 1, equal
current char of text1: a, current char of text2: a
current_text1: a, current_text2: a
dp[i][j]: 1, dp[i-1][j-1]: 0
current text1 index: 1, current text2 index: 2, not equal
current char of text1: a, current char of text2: c
current_text1: a, current_text2: ac
dp[i][j]: 1, dp[i-1][j]: 0, dp[i][j-1]: 1
current text1 index: 1, current text2 index: 3, not equal
current char of text1: a, current char of text2: e
current_text1: a, current_text2: ace
dp[i][j]: 1, dp[i-1][j]: 0, dp[i][j-1]: 1
current text1 index: 2, current text2 index: 1, not equal
current char of text1: b, current char of text2: a
current_text1: ab, current_text2: a
dp[i][j]: 1, dp[i-1][j]: 1, dp[i][j-1]: 0
current text1 index: 2, current text2 index: 2, not equal
current char of text1: b, current char of text2: c
current_text1: ab, current_text2: ac
dp[i][j]: 1, dp[i-1][j]: 1, dp[i][j-1]: 1
current text1 index: 2, current text2 index: 3, not equal
current char of text1: b, current char of text2: e
current_text1: ab, current_text2: ace
dp[i][j]: 1, dp[i-1][j]: 1, dp[i][j-1]: 1
current text1 index: 3, current text2 index: 1, not equal
current char of text1: c, current char of text2: a
current_text1: abc, current_text2: a
dp[i][j]: 1, dp[i-1][j]: 1, dp[i][j-1]: 0
current text1 index: 3, current text2 index: 2, equal
current char of text1: c, current char of text2: c
current_text1: abc, current_text2: ac
dp[i][j]: 2, dp[i-1][j-1]: 1
current text1 index: 3, current text2 index: 3, not equal
current char of text1: c, current char of text2: e
current_text1: abc, current_text2: ace
dp[i][j]: 2, dp[i-1][j]: 1, dp[i][j-1]: 2
current text1 index: 4, current text2 index: 1, not equal
current char of text1: d, current char of text2: a
current_text1: abcd, current_text2: a
dp[i][j]: 1, dp[i-1][j]: 1, dp[i][j-1]: 0
current text1 index: 4, current text2 index: 2, not equal
current char of text1: d, current char of text2: c
current_text1: abcd, current_text2: ac
dp[i][j]: 2, dp[i-1][j]: 2, dp[i][j-1]: 1
current text1 index: 4, current text2 index: 3, not equal
current char of text1: d, current char of text2: e
current_text1: abcd, current_text2: ace
dp[i][j]: 2, dp[i-1][j]: 2, dp[i][j-1]: 2
current text1 index: 5, current text2 index: 1, not equal
current char of text1: e, current char of text2: a
current_text1: abcde, current_text2: a
dp[i][j]: 1, dp[i-1][j]: 1, dp[i][j-1]: 0
current text1 index: 5, current text2 index: 2, not equal
current char of text1: e, current char of text2: c
current_text1: abcde, current_text2: ac
dp[i][j]: 2, dp[i-1][j]: 2, dp[i][j-1]: 1
current text1 index: 5, current text2 index: 3, equal
current char of text1: e, current char of text2: e
current_text1: abcde, current_text2: ace
dp[i][j]: 3, dp[i-1][j-1]: 2

代码：

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [[0 for _ in range(len(text2) + 1)] for __ in range(len(text1) + 1)]
        for i in range(1, len(text1) + 1):
            for j in range(1, len(text2) + 1):
                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[-1][-1]