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