問題描述
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
問題分析
雖然是一道hard題盏缤，但我做的時候思路很明確峻黍，雖然與普通思路好像不太一樣，但效果出奇地好……
- 我想的是設(shè)置p1(s1)、p2(s2)间涵、p3(s3)三個指針桩皿，p3每挪一位香缺，與p1坐漏、p2處字母比較，根據(jù)比較結(jié)果進(jìn)行指針移動职员，如果出現(xiàn)兩可的選擇麻蹋，則進(jìn)行遞歸調(diào)用。但如果單純這么做焊切，會超時扮授，因為重復(fù)的枝太多。因此設(shè)置一個記錄不可行狀態(tài)的set专肪，每次出現(xiàn)失敗時刹勃，將(p1, p3)加入狀態(tài)集，根據(jù)這個狀態(tài)集進(jìn)行剪枝嚎尤。
不過這樣寫出來的代碼很長很難看荔仁，不知道是不是我代碼風(fēng)格還不夠好。 - 看了一下九章算術(shù)上的方法，用的是動規(guī)咕晋，代碼比較簡潔。
AC代碼
class Solution(object):
def isInterleave(self, s1, s2, s3):
"""
:type s1: str
:type s2: str
:type s3: str
:rtype: bool
"""
self.record = set([])
self.n1 = len(s1)
self.n2 = len(s2)
self.n3 = len(s3)
self.s1 = s1
self.s2 = s2
self.s3 = s3
if self.n3 != self.n2 + self.n1:
return False
return self.sub(0,0,0)
def sub(self, p1, p2, p3):
while p3 < self.n3:
if p1 == self.n1 or p2 == self.n2:
break
if self.s1[p1] == self.s3[p3] and self.s2[p2] == self.s3[p3]:
f1 = (p1+1, p3+1) in self.record
f2 = (p1, p3+1) in self.record
if f1 and f2:
self.record.add((p1, p3))
return False
if f1 and not f2:
if self.sub(p1, p2+1, p3+1):
return True
else:
self.record.update((p1, p3+1), (p1, p3))
return False
if f2 and not f1:
if self.sub(p1+1, p2, p3+1):
return True
else:
self.record.update((p1+1, p3+1), (p1, p3))
return False
else:
if self.sub(p1, p2+1, p3+1) or self.sub(p1+1, p2, p3+1):
return True
else:
self.record.add((p1, p3))
return False
elif self.s1[p1] == self.s3[p3] and self.s2[p2] != self.s3[p3]:
if (p1+1, p3+1) not in self.record:
p1 += 1
p3 += 1
else:
self.record.update((p1+1, p3+1), (p1, p3))
return False
elif self.s1[p1] != self.s3[p3] and self.s2[p2] == self.s3[p3]:
if (p1, p3+1) not in self.record:
p2 += 1
p3 += 1
else:
self.record.update((p1, p3+1), (p1, p3))
return False
else:
self.record.add((p1, p3))
return False
if p1 == self.n1:
if self.s3[p3:] == self.s2[p2:]:
return True
else:
self.record.add((p1, p3))
return False
if p2 == self.n2:
if self.s3[p3:] == self.s1[p1:]:
return True
else:
self.record.add((p1, p3))
return False
Runtime: 48 ms, which beats 95.07% of Python submissions.
class Solution(object):
def isInterleave(self, s1, s2, s3):
"""
:type s1: str
:type s2: str
:type s3: str
:rtype: bool
"""
if len(s1) + len(s2) != len(s3):
return False
f = [[False for i in range(len(s1) + 1)] for j in range(len(s2) + 1)]
f[0][0] = True
for i in range(len(s1)):
f[0][i+1] = s1[:i+1] == s3[:i+1]
for i in range(len(s2)):
f[i+1][0] = s2[:i+1] == s3[:i+1]
for i in range(len(s2)):
for j in range(len(s1)):
if s1[j] == s3[i+j+1]:
f[i+1][j+1] = f[i+1][j]
if s2[i] == s3[i+j+1]:
f[i+1][j+1] |= f[i][j+1]
return f[len(s2)][len(s1)]
Runtime: 84 ms, which beats 26.76% of Python submissions.
