[leetcode/lintcode 題解] 阿裡算法面試真題：交叉字元串

描述

給出三個字元串:s1、s2、s3，判斷s3是否由s1和s2交叉構成。

線上評測位址：

領扣題庫官網

樣例1
輸入:
"aabcc"
"dbbca"
"aadbbcbcac"
輸出:
true           

樣例2
輸入:
""
""
"1"
輸出:
false           

樣例3
輸入:
"aabcc"
"dbbca"
"aadbbbaccc"
輸出:
false           

算法：動态規劃

動态規劃。 dpi代表由s1的前i個字母和s2的前j個字母是否能構成目前i+j個字母。 然後狀态轉移即可。（看第i+j+1個是否能被s1的第i+1個構成或被s2的第j+1個構成）

class Solution:
    """
    @params s1, s2, s3: Three strings as description.
    @return: return True if s3 is formed by the interleaving of
             s1 and s2 or False if not.
    @hint: you can use [[True] * m for i in range (n)] to allocate a n*m matrix.
    """
    def isInterleave(self, s1, s2, s3):
        # write your code here
        if s1 is None or s2 is None or s3 is None:
            return False
        if len(s1) + len(s2) != len(s3):
            return False

        interleave = [[False] * (len(s2) + 1) for i in range(len(s1) + 1)]
        interleave[0][0] = True
        for i in range(len(s1)):
            interleave[i + 1][0] = s1[:i + 1] == s3[:i + 1]
        for i in range(len(s2)):
            interleave[0][i + 1] = s2[:i + 1] == s3[:i + 1]

        for i in range(len(s1)):
            for j in range(len(s2)):
                interleave[i + 1][j + 1] = False
                if s1[i] == s3[i + j + 1]:
                    interleave[i + 1][j + 1] = interleave[i][j + 1]
                if s2[j] == s3[i + j + 1]:
                    interleave[i + 1][j + 1] |= interleave[i + 1][j]
        return interleave[len(s1)][len(s2)]           

更多題解參考：

九章官網solution