A fast python divide and conquer solution?


  • 0
    E

    Hi Guys, I have to acknowledge that I am not supper good at divide and conquer algorithms and I am trying to understand it right now. But I think my solution is a divide and conquer solution. Please let me know your comments. That might help me to improve. Thanks in advance.

    The main idea is to compare the last character of s3 to that of s2 and s1 in each recursion.

    If s3[-1] != s1[-1] and s3[-1] != s2[-1] return false;

    If s3[-1] == s1[-1] == s2[-1] then compare s1[0:-1], s2, s3[0:-1] and s1, s2[0:-1], s3[0:-1] and return the or of the two results;

    Else if s3[-1] == s1[-1] then compare s1[0:-1], s2, s3[0:-1] and return;

    Else if s3[-1] == s2[-1] then compare s1, s2[0:-1], s3[0:-1] and return;

    The code is showed below.

    class Solution:
    # @return a boolean
    def isInterleave(self, s1, s2, s3):
        compared_pairs = {}
        return self.recursionCheck(s1, s2, s3, len(s1)-1, len(s2)-1, len(s3)-1, compared_pairs)
    
    def recursionCheck(self, s1, s2, s3, p1, p2, p3, compared):
        n1, n2, n3 = p1 + 1, p2 + 1, p3 + 1
        if n1 == 0 and n2 == 0 and n3 == 0:
            return True
        if n3 != (n1 + n2):
            return False
        if (p1,p2,p3) in compared:
            return compared[(p1,p2,p3)]
        interleave = False
        if n1 != 0 and n2 != 0 and s3[p3] == s1[p1] and s3[p3] == s2[p2]:
            interleave = self.recursionCheck(s1, s2, s3, p1-1,p2,p3-1, compared) or self.recursionCheck(s1, s2, s3, p1, p2-1,p3-1, compared)
        elif n1 != 0 and s3[p3] == s1[p1]:
            interleave = self.recursionCheck(s1, s2, s3, p1-1, p2, p3-1, compared)
        elif n2 != 0 and s3[p3] == s2[p2]:
            interleave = self.recursionCheck(s1, s2, s3, p1, p2-1, p3-1, compared)
        compared[(p1,p2,p3)] = interleave
        return interleave

Log in to reply
 

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