蠡口97. Interleaving String

拿到题，提笔就写分治，结果超时。那很可能需要记录过程，而且这题返回T or F，很像DP。

1）建立矩阵：dp[i][j]表示isTnterleave(s1[0:i], s2[0:j], s3[0:(i+j)])的值，也就是下图中紫色部分是否可以由红色部分和蓝色部分交替拼接组成。dp的初始值全为F

2）初始化边界：

　　dp[0][0]表示isTnterleave("","",""),当然为T；

　　当dp[i-1][0]为T（即s3[0:(i-1)]==s1[0:(i-1)]）且s3[i-1]==s1[i-1]时，dp[i][0]为T；
　　当dp[0][j-1]为T（即s3[0:(j-1)]==s2[0:(j-1)]）且s3[j-1]==s2[j-1]时，dp[0][j]为T；

3）建立递推关系：

　　当dp[i-1][j]为T且s1[i-1]==s3[i+j-1]时，也就是说i+j-1之前都匹配了，最后一个字符由s1来凑，dp[i][j]为T

　　当dp[i][j-1]为T且s2[j-1]==s3[i+j-1]时，也就是说i+j-1之前都匹配了，最后一个字符由s2来凑，dp[i][j]为T

4）返回值：应当返回dp[len(s1)][len(s2)]，表示s1的全部和s2的全部是否可以交替拼接组成s3

class Solution(object):
    def isInterleave(self, s1, s2, s3):
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: bool
        """
        if len(s3)!=len(s1)+len(s2): return(False)
        dp=[[False for j in range(len(s2)+1)] for i in range(len(s1)+1)]
        dp[0][0]=True
        for i in range(1,len(s1)+1): dp[i][0]=dp[i-1][0] and s1[i-1]==s3[i-1]
        for j in range(1,len(s2)+1): dp[0][j]=dp[0][j-1] and s2[j-1]==s3[j-1]
        for i in range(1,len(s1)+1):
            for j in range(1,len(s2)+1):
                if dp[i-1][j] and s1[i-1]==s3[i+j-1]: dp[i][j]=True
                if dp[i][j-1] and s2[j-1]==s3[i+j-1]: dp[i][j]=True
        return(dp[len(s1)][len(s2)])