本文共 3583 字，大约阅读时间需要 11 分钟。

leetcode 97  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. 法一：递归，该方法能求得问题的解，但会超时。。。

Python代码：

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)): #若s1与s2的长度之和跟s3的长度不相等，则肯定不满足题意，直接返回False            return False        else:            return self.recursion(s1,0,s2,0,s3,0) #若二者长度相等，则通过调用recursion()函数来判断是否满足题意        def recursion(self,str1,p1,str2,p2,str3,p3):        if p3==len(str3): #在 s1与s2的长度之和跟s3的长度相等 的条件下，若p3==len(str3)为真，则说明满足题意。            return True        '''         单纯的通过p3==len(str3)并不能得出符合题意的结论，比如s1='abcd',s2='fe',s3='abcf',         在递归调用recursion()函数的过程中，p3==len(str3)最终为真，返回True，得到一个错误的结论。为了避免这种错误，         我们需要在isInterleave()函数中需要检查s1与s2的长度之和跟s3的长度是否相等，保证只有在二者相等的条件下，         才去调用recursion()函数          '''        if p1==len(str1): #若str1已经遍历完毕，则只需要判断str2和str3剩下的部分是否相等            return str2[p2:]==str3[p3:]        if p2==len(str2): #若str2已经遍历完毕，则只需要判断str1和str3剩下的部分是否相等            return str1[p1:]==str3[p3:]                '''若str1的当前字符 和 str2中的当前字符 都与 str3的当前字符 相等，则此时有2条路可以走：        1》将p1和p3同时加1        2》将p2和p3同时加1        这2条路只要有1条走的通，则返回True，满足 或 关系，因此需要用 or 连接这2条路所代表的2种情况，如下：        '''        if str1[p1]==str3[p3] and str2[p2]==str3[p3]:            return self.recursion(str1,p1+1,str2,p2,str3,p3+1) or self.recursion(str1,p1,str2,p2+1,str3,p3+1)        elif str1[p1]==str3[p3]: #只有str1中的当前字符 与 str3中的当前字符 相等，则将p1和p3同时加1            return self.recursion(str1,p1+1,str2,p2,str3,p3+1)        elif str2[p2]==str3[p3]: #只有str2中的当前字符 与 str3中的当前字符 相等，则将p2和p3同时加1            return self.recursion(str1,p1,str2,p2+1,str3,p3+1)        else: #若str1的当前字符 和 str2中的当前字符 都与 str3的当前字符 不相等，则说明不满足题意，返回False            return False

法二：使用 动态规划 可以在限定时间内求得问题的解 分析： 关于DP矩阵每一个格子所代表的意义看下面这一个图： （以下描述为 1 base） DP[i][j]表示s1取前i位，s2取前j位，检查是否能组成s3的前i+j位。 举个列子，注意左上角那一对箭头指向的格子DP[1][1], 表示s1取第1位a, s2取第1位d，是否能组成s3的前两位aa。 从DP[0][1] 往下的箭头表示，s1目前取了前0位，s2目前取了1位，添加s1的第1位，检查它是否等于s3的第2（i+j）位。 从DP[1][0] 往右的箭头表示，s1目前取了1位，s2目前取了0位，我们添加s2的第1位，检查它是否等于s3的第2（i+j）位。 那什么时候取True，什么时候取False呢？ 如果新添加的字符，不等于s3里面对应的第（i+j）位，则取False。 若要取True，必须同时满足2个条件： 1》新添加的字符，要等于s3里面对应的第（i+j）位。 2》该格子的前一个格子也要等于True，为什么呢？我们举一个游戏的例子来形象的解释一下：在游戏中，通过一关为True,未通过为False。若第8关为True,则其前一关（第7关）必须也为True。因为若第7关为False，就 game over 了，根本就不会进入第8关，自然也不会取得第8关为True这样的结果。同理，若第7关为True，则第6关也必须为True，以此类推。。。 (以下讨论是 0 base) 此外，还有4个地方需要注意： 1》初始时，应将DP[0][0]设为True。 2》对于DP中的第0行（除了DP[0][0]）中的每一个格子，它的前一步是其左边的格子。 3》对于DP中的第0列（除了DP[0][0]）中的每一个格子，它的前一步是其上边的格子。 4》对于DP中的其他格子(即DP[i][j],i>0,j>0)，它的前一步是其左边的或其上边的格子，在这个情况下，有2条路径可以到达DP[i][j]，只要有一条路径走得通，DP[i][j]就设为True。 python代码：

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        DP=[[False]*(len(s2)+1) for i in range(len(s1)+1)]        for i in range(len(s1)+1):            for j in range(len(s2)+1):                if i==0 and j==0:                    DP[i][j]=True                elif i>0 and DP[i-1][j] and s3[i+j-1]==s1[i-1]:                    DP[i][j]=True                elif j>0 and DP[i][j-1] and s3[i+j-1]==s2[j-1]:                    DP[i][j]=True                else: #由于DP被初始化为全False，因此，该else语句可以省去                    DP[i][j]=False        return DP[len(s1)][len(s2)]