Python 12 Lines DP


  • 0
    class Solution(object):
        def isInterleave(self, s1, s2, s3):
            if len(s1)+len(s2) != len(s3):
                return False
            row = [True]*(len(s2)+1)
            for j in range(1, len(row)):
                row[j] = row[j-1] and s2[j-1]==s3[j-1]
            for i in range(len(s1)):
                row[0] = row[0] and s1[i]==s3[i]
                for j in range(1, len(row)):
                    row[j] = (row[j] and s1[i]==s3[i+j]) or (row[j-1] and s2[j-1]==s3[i+j])
            return row[-1]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.