原题
给出两个字符串，找到最长公共子序列(LCS)，返回LCS的长度。
给出"ABCD" 和 "EDCA"，这个LCS是 "A" (或 D或C)，返回1
给出** "ABCD"** 和 "EACB"，这个LCS是"AC"返回 2
解题思路
- 双序列型动态规划 - Two Sequence DP
-
cache[i][j]表示第一个字符串的前i个字符和第二个字符串的前j个字符的最长公共子序列的长度 - 状态转移方程：
- 如果
str1[i] != str2[j]
cache[i][j] = max(cache[i][j - 1], cache[i - 1][j]) - 如果
str1[i] != str2[j]
cache[i - 1][j - 1] + 1
完整代码
class Solution:
"""
@param A, B: Two strings.
@return: The length of longest common subsequence of A and B.
"""
def longestCommonSubsequence(self, A, B):
if not A or not B:
return 0
cache = [[0 for i in range(len(A) + 1)] for j in range(len(B) + 1)]
for i in range(1, len(B) + 1):
for j in range(1, len(A) + 1):
if A[j - 1] == B[i - 1]:
cache[i][j] = cache[i - 1][j - 1] + 1
else:
cache[i][j] = max(cache[i][j - 1], cache[i - 1][j])
return cache[len(B)][len(A)]
