本文共 694 字，大约阅读时间需要 2 分钟。

## longest common subsequence# @param s1 string字符串 the string# @param s2 string字符串 the string# @return string字符串#class Solution:    def LCS(self , s1 , s2 ):        # write code here        dp = [[""] * (len(s2)+1) for _ in range(len(s1)+1)]        for i in range(1, len(s1)+1):            for j in range(1, len(s2)+1):                if s1[i-1] == s2[j-1]:                    dp[i][j] = dp[i-1][j-1] + s1[i-1]                else:                    if len(dp[i][j-1]) < len(dp[i-1][j]):                        dp[i][j] = dp[i-1][j]                    else:                        dp[i][j] = dp[i][j-1]        if dp[-1][-1] == "":            return -1        else:            return dp[-1][-1]