Leetcode 97: Interleaving String

https://leetcode.com/problems/interleaving-string/

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.

 

Code

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
        if not s1:
            return s3 == s2
        if not s2:
            return s3 == s1
        
        res = [[False] * (len(s1)+1) for _ in xrange(len(s2)+1)]
        
        for i in xrange(len(s1)+1):
            res[0][i] = (s1[:i] == s3[:i])
        for j in xrange(len(s2)+1):
            res[j][0] = (s2[:j] == s3[:j])
        
        for j in xrange(1, len(s2)+1):
            for i in xrange(1, len(s1)+1):
                res[j][i] = (res[j][i-1] and (s3[i+j-1] == s1[i-1])) or (res[j-1][i] and (s3[i+j-1]==s2[j-1]))
        
        return res[-1][-1]
        

 

Idea

Use DP. `res[j][i]` is the boolean indicator of whether `s3[:i+j]` is an interleaving string of `s1[:i]` and `s2[:j]`. It can be written recursively as `res[j][i] = (res[j][i-1] and (s3[i+j-1] == s1[i-1])) or (res[j-1][i] and (s3[i+j-1]==s2[j-1]))`. 

 

Reference

http://tianmaying.com/tutorial/LC97