原題
給出兩個(gè)字符串蔓肯，找到最長(zhǎng)公共子序列(LCS)搀绣，返回LCS的長(zhǎng)度。
給出"ABCD" 和 "EDCA"恰聘，這個(gè)LCS是 "A" (或 D或C)句各，返回1
給出** "ABCD"** 和 "EACB"，這個(gè)LCS是"AC"返回 2
解題思路
- 雙序列型動(dòng)態(tài)規(guī)劃 - Two Sequence DP
-
cache[i][j]表示第一個(gè)字符串的前i個(gè)字符和第二個(gè)字符串的前j個(gè)字符的最長(zhǎng)公共子序列的長(zhǎng)度 - 狀態(tài)轉(zhuǎn)移方程：
- 如果
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)]
