class Solution:
# @return a boolean
def isInterleave(self, s1, s2, s3):
n=len(s1)
m=len(s2)
l=len(s3)
if l!=n+m:return False
match=[[True]*(m+1) for i in range(n+1)]
for i in range(1,n+1):
match[i][0]=match[i-1][0] and s1[i-1]==s3[i-1]
for j in range(1,m+1):
match[0][j]=match[0][j-1] and s2[j-1]==s3[j-1]
for i in range(1,n+1):
for j in range(1,m+1):
match[i][j]=(s3[i+j-1]==s1[i-1] and match[i-1][j]) or (s3[i+j-1]==s2[j-1] and match[i][j-1])
return match[n][m]
Friday, September 19, 2014
Leetcode: Interleaving String @Python
Subscribe to:
Post Comments
(
Atom
)
No comments :
Post a Comment