Given two strings, find the longest common subsequence (LCS).

Example

Example 1:
	Input:  "ABCD" and "EDCA"
	Output:  1
	
	Explanation:
	LCS is 'A' or  'D' or 'C'


Example 2:
	Input: "ABCD" and "EACB"
	Output:  2
	
	Explanation: 
	LCS is "AC"

这个题目思路是利用dynamic programming，用二维的，mem[l1 + 1][l2 + 1] # mem[i][j] 去表示s1的前i个characters与s2的前j个characters的LCS的length。
function ： mem[i][j] = max(mem[i][j - 1], mem[i - 1][j]) if s1[i - 1] != s2[j - 1]
　　　　　　　　　　　　　　max(mem[i][j - 1], mem[i - 1][j], mem[i - 1][j - 1] + 1)   if s1[i - 1] == s2[j - 1]
initialize : mem[i][0] = mem[0][j] = 0

Code:
class Solution:
    def LCS(self, s1, s2):
        l1, l2 = len(s1), len(s2)
        mem = [[0] * (l2 + 1) for _ in range(l1)]
        for i in range(1, l1 + 1): 
            for j in range(1, l2 + 1):
                mem[i][j] = max(mem[i - 1][j], mem[i][j - 1])
                if s1[i - 1] == s2[j - 1]:
                    mem[i][j] = max(mem[i][j], mem[i - 1][j - 1] + 1)
        return mem[l1][l2]

 

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。 
 
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄