| FazBrowse GitHub Viewer | Trending | | Home |
| Tools: [Download Repo ZIP] [Original HTTPS Page] |
| Name | Name | Last commit date | ||
|---|---|---|---|---|
parent directory.. | ||||
| layout | post |
|---|---|
| title | (Dynamic Programming) Longest Common Subsequence |
给定两个字符串，找出两个字符串包含的最长子串。
此题是一道典型的动态规划，下面给出分析步骤。
假设两个字符串分别为 'abcdef', 'acbcf' 初始状态如下：
| 字符串 | a | b | c | d | e | f | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| a | 0 | ||||||
| c | 0 | ||||||
| b | 0 | ||||||
| c | 0 | ||||||
| f | 0 |
第一步：如果第二个字符串只有一个字符，那么得到下表
| 字符串 | a | b | c | d | e | f | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| c | 0 | ||||||
| b | 0 | ||||||
| c | 0 | ||||||
| f | 0 |
依次向右比较的过程中，发现第二个字符串中的 'a' 于第一个字符串中的 'a' 相等，此时dp[1][1] = 1 + dp[0][0] = 1。 之所以要加上dp[0][0]，是因为发现相等字符以后，还要加上去掉当前字符后，之前出现的最大子串长度，此时因为第二个字符串只有 'a'，所以当前只能取dp[0][0]。 而当接着向后比较的过程中，并没有再次出现相等的情形，所以dp[1][1 + n] = 1，都取上一次出现的最大值。
第二步：使用第二个字符串中的下一个字符，那么得到下表
| 字符串 | a | b | c | d | e | f | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| c | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
| b | 0 | ||||||
| c | 0 | ||||||
| f | 0 |
此时有两点需要说明。 1. 当 'c' 与 'a' 进行比较时，发现不相等，此时要取左边或者上边数字较大者。其实也很好理解，取左边意味着取 'c' 之前得到的最大子串长度，取上边意味着取去掉 'c' 得到的最大子串长度。 2. 当发现 'c' 相等时。dp[2][3] = 1 + dp[2 - 1][3 - 1]。也就是要加上两个字符串都去掉 'c' 之后得到的最长子串的长度。
以此类推，得到最终的表格
| 字符串 | a | b | c | d | e | f | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| c | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
| b | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
| c | 0 | 1 | 2 | 3 | 3 | 3 | 3 |
| f | 0 | 1 | 2 | 3 | 3 | 3 | 4 |
可以得出转移方程:
max(dp[i - 1][j], dp[i][j - 1] if 当前字符不相等
dp[i][j] =
dp[i - 1][j - 1] + 1 if 当前字符相等
class Solution():
def do(self, str1, str2):
len_str1, len_str2 = len(str1), len(str2)
dp = [[0] * (len_str1 + 1) for _ in range(len_str2 + 1)]
'''
dp[i][j] =
max(dp[i - 1][j], dp[i][j - 1]) if str1[j] != str2[i]
dp[i - 1][j - 1] + 1 if str1[j] == str2[i]
'''
for i in range(1, len_str2 + 1):
for j in range(1, len_str1 + 1):
if str1[j - 1] == str2[i - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[-1][-1]
solution = Solution()
print solution.do('abcdef', 'acbcf')
print solution.do('abcdca', 'acbc')| Back | FazBrowse Home | New Git URL |