最长公共子序列
简介
最长公共子序列(Longest Common Subsequence),英文缩写为LCS。其定义是,一个序列 S,如果分别是两个或多个已知序列的子序列,且是所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列。
应用
应用1:Leetcode.1143
题目
解题思路
动态规划
设 \(dp[i][j]\) 表示字符串 \(text_1\) 的前 \(i\) 个字符,与字符串 \(text_2\) 的前 \(j\) 个字符的最长公共子序列。
即子串 \(text_1[:i-1]\) 与 \(text_2[:j-1]\) 的最长公共子序列的长度,注意,数组序号是从 \(0\) 开始的,\(i-1\) 表示前 \(i\) 个字符,那么:
初始状态
当其中一个字符串的长度为 \(0\) 时,没有公共子序列,所以,任意一个字符长度为 \(0\) 时,最长公共子序列的长度为 \(0\) ,即:
\[\begin{align} dp[0][j] = 0 \\ dp[i][0] = 0 \end{align} \]状态转移
我们分别枚举两个字符串,会出现两种情况:
- 如果当前两个字符相等,那么当前状态 \(dp[i][j]\) 就可以由上一个状态 \(dp[i - 1][j - 1]\) 加 \(1\) ;
- 如果当前两个字符不相等,那么当前状态 \(dp[i][j]\) 就要从 \(dp[i][j - 1]\) 或者 \(dp[i - 1][j]\) 中取最大值。
所以,状态转移方程如下:
\[dp[i][j]= \begin{cases} dp[i - 1][j - 1] + 1, & text_1[i] = text_2[j] \\ max(dp[i][j - 1],\ dp[i - 1][j]), & text_1[i] \neq text_2[j] \\ \end{cases} \]代码实现
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
# 如果当前两个字符串中的字符相等,则直接移动两个字符串的指针
if text1[i -1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
return dp[m][n]
标签:text,字符串,公共,序列,最长,dp
From: https://www.cnblogs.com/larry1024/p/16901783.html