注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号 
x
两个题:
583. Delete Operation for Two Strings:https://leetcode.com/problems/de ... trings/description/
代码:
class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
dp=[[0 for _ in range(len(word2)+1)] for _ in range(len(word1)+1)]
for i in range(1, len(word1)+1):
for j in range(1, len(word2)+1):
if word1[i-1]==word2[j-1]:
dp[i][j]=dp[i-1][j-1]+1
else: dp[i][j]=max(dp[i-1][j], dp[i][j-1])
return len(word1)+len(word2)-2*dp[-1][-1]
718. Maximum Length of Repeated Subarray:https://leetcode.com/problems/ma ... barray/description/
代码:
class Solution:
def findLength(self, A, B):
"""
:type A: List[int]
:type B: List[int]
:rtype: int
"""
result=0
dp=[[0 for _ in range(len(B)+1)] for _ in range(len(A)+1)]
for i in range(1, len(A)+1):
for j in range(1, len(B)+1):
if A[i-1]==B[j-1]:
dp[i][j]=dp[i-1][j-1]+1
result=max(result, dp[i][j])
return result
两段代码的思路其实是一样的,都是找到最长的公共字符串。但是583多了一段加粗的内容,不知道为什么要加这一段。不加就是错的。
求大神讲解原因,为什么会有多一段的else处理。感觉两个题的逻辑都对,但是不能互换。
先谢谢了。
|