Python short and concise DP solution O(mn) time


  • 0

    Maintain an m by n matrix res to store the contemporary results, where m and n are the lengths of s1 and s2, respectively.

    res[i][j] represents the boolean value whether s1[0:i] and s2[0:j] can form interleaving string s3[0:i+j],

    A recursive relation is hence:

    condition1: res[i-1][j] is True and i-th char of s1 equals (i+j)th char of s3;
    condition2: res[i][j-1] is True and j-th char of s2 equals (i+j)th char of s3

    The validity of either condition 1 or 2 marks res[i][j] as True.

    An AC solution is provided as follows. The time complextiy is apparently O(mn) and also the space complexity, while the later one can be optimized to O(min(m,n)).

    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
            
            nrow, ncol = len(s1), len(s2)
            res = [[None for _ in range(ncol+1)] for _ in range(nrow+1)]
            res[0][0] = True
            
            for i in range(1, nrow+1):
                res[i][0] = res[i-1][0] and (s1[i-1] == s3[i-1])
                
            for j in range(1, ncol+1):
                res[0][j] = res[0][j-1] and (s2[j-1] == s3[j-1])
            
            for i in range(1, nrow+1):
                for j in range(1, ncol+1):
                    bool1 = res[i-1][j] and (s1[i-1] == s3[i+j-1])
                    bool2 = res[i][j-1] and (s2[j-1] == s3[i+j-1])
                    res[i][j] = (bool1 or bool2)
                    
            return res[nrow][ncol]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.