Leetcode刷题(15) 双字符串的问题

多用双指针和动态规划

1143. 最长公共子序列

具体方法参考labuladong经典动态规划：最长公共子序列

方法一: 自底向下的递归(双指针)

class Solution(object): def longestCommonSubsequence(self, text1, text2): """ :type text1: str :type text2: str :rtype: int """ mome = dict() def dp(i, j): # base case if i == -1: return 0 if j == -1: return 0 # 已经存在备忘录中直接返回 if (i, j) in mome.keys(): return mome[(i, j)] else: # 都在, 那公共子序列+1 if text1[i] == text2[j]: mome[(i, j)] = 1 + dp(i-1, j-1) else: mome[(i, j)] = max( dp(i-1, j), # text1不在 dp(i, j-1) # text2不在 ) return mome[(i, j)] return dp(len(text1) - 1, len(text2) - 1)

方法二: 自底向上的动态规划

class Solution(object): def longestCommonSubsequence(self, text1, text2): """ :type text1: str :type text2: str :rtype: int """ num1 = len(text1) num2 = len(text2) # shape of dp = (num1 + 1, num2 + 1) dp = [[0] * (num2 + 1) for _ in range(num1 + 1)] # base case for i in range(1, num1 + 1): for j in range(1, num2 + 1): # 两个text的当前字符都在公共子序列中 if text1[i - 1] == text2[j - 1]: dp[i][j] = dp[i-1][j-1] + 1 else: # 至少有一个不在公共子序列中(都不在的包含在里面, 这次text1中的元素不在, 下次text2中的元素不在这不就其了) dp[i][j] = max( dp[i-1][j], # text1的第i个元素不在公共子序列中 dp[i][j-1] # text2的第i个元素不在公共子序列中 ) return dp[num1][num2]

72. 编辑距离

方法一: 自顶向下的递归, 几乎和上一题一样

class Solution(object): def minDistance(self, word1, word2): """ :type word1: str :type word2: str :rtype: int """ # 备忘录 mome = dict() def dp(i, j): # base case if i == -1: return j + 1 if j == -1: return i + 1 if (i, j) in mome: return mome[(i, j)] else: if word1[i] == word2[j]: mome[(i,j)] = dp(i-1, j-1) # 跳过 else: mome[(i, j)] = min( dp(i - 1, j), # 删除 dp(i - 1, j - 1), # 替换 dp(i, j - 1) # 在i后面插入word2[j] ) + 1 return mome[(i, j)] return dp(len(word1) - 1, len(word2) - 1)

方法二: 动态规划

class Solution(object): def minDistance(self, word1, word2): """ :type word1: str :type word2: str :rtype: int """ # 备忘录 n1 = len(word1) n2 = len(word2) dp = [[0] * (n2 + 1) for _ in range(n1 + 1)] # base case注意这个基础情况 for i in range(1, n1 + 1): dp[i][0] = i for j in range(1, n2 + 1): dp[0][j] = j for i in range(1, n1 + 1): for j in range(1, n2 + 1): if word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] # 跳过 else: dp[i][j] = min( dp[i-1][j-1], # 替换 dp[i][j-1], # 插入 dp[i-1][j] # 删除 ) + 1 # 记得操作了一次之后次数+1 return dp[-1][-1]

最大公共子串

具体方法参考求两个字符串的最长公共子串

class Solution(object): def lcs(self, str1, str2): n1 = len(str1) n2 = len(str2) dp = [[0] * (n2 + 1) for _ in range(n1 + 1)] max_len = 0 for i in range(1, n1 + 1): for j in range(1, n2 + 1): if str1[i-1] == str2[j-1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = 0 max_len = max(dp[i][j], max_len) return max_len