问题描述
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题，但我做的时候思路很明确，虽然与普通思路好像不太一样，但效果出奇地好……
- 我想的是设置p1(s1)、p2(s2)、p3(s3)三个指针，p3每挪一位，与p1、p2处字母比较，根据比较结果进行指针移动，如果出现两可的选择，则进行递归调用。但如果单纯这么做，会超时，因为重复的枝太多。因此设置一个记录不可行状态的set，每次出现失败时，将(p1, p3)加入状态集，根据这个状态集进行剪枝。
不过这样写出来的代码很长很难看，不知道是不是我代码风格还不够好。 - 看了一下九章算术上的方法，用的是动规，代码比较简洁。
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.
