Interleaving String

Given three strings: s1, s2, s3, determine whether s3 is formed by the interleaving of s1 and s2.

Example

For s1 = "aabcc", s2 = "dbbca"

When s3 = "aadbbcbcac", return true.

When s3 = "aadbbbaccc", return false.

Solution

state: f[i][j]表示s1的前i个字符和s2的前j个字符能否交替组成s3的前i+j个字 符 function: f[i][j] = (f[i-1][j] && (s1[i-1]==s3[i+j-1]) ||

(f[i][j-1] && (s2[j-1]==s3[i+j-1]) initialize: f[i][0] = (s1[0..i-1] == s3[0..i-1]) f[0][j] = (s2[0..j-1] == s3[0..j-1])

answer: f[n][m], n = sizeof(s1), m = sizeof(s2)

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
        m , n = len(s1), len(s2)
        if m + n != len(s3):
            return False
        f = [[False] * (n + 1) for x in range(m + 1)]

        f[0][0] = True 

        for i in range(1, m + 1):
            if s1[i - 1] == s3[i - 1] and f[i - 1][0]:
                f[i][0] = True
        for i in range(1, n + 1):
            if s2[i - 1] == s3[i - 1] and f[0][i - 1]:
                f[0][i] = True
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if (s1[i - 1] == s3[i + j - 1] and f[i - 1][j]) or (s2[j - 1] == s3 [i + j - 1] and f[i][j - 1]):
                    f[i][j] = True
        return f[m][n]