7.3 - hard - 22

97. Interleaving String
첫 번째 사고방식은 Recursion인데 TLE가 됐어요. DP로 한 것 같아요. DP로도 한 셈이에요. 그런데 약간의 의문이 있어요. s3을 검사할 때 1번부터 검사해야 해요. 0번이 아니라 1번부터 검사해야 해요. 생각해보면 s3[0]이 초기화할 때 이미 초기화되었어요.umm. 어쨌든 약간 tricky인 것 같아요.

class Solution(object):
   def isInterleave(self, s1, s2, s3):
       """
       :type s1: str
       :type s2: str
       :type s3: str
       :rtype: bool
       """
       print s1, s2, s3
       if len(s3) != len(s1) + len(s2):
           return False
       if not s1 and not s2 and not s3:
           return True
       if not s1:
           return s2 == s3
       if not s2:
           return s1 == s3
       
       if s1[0] == s2[0]:
           if s3[0] == s1[0]:
               return self.isInterleave(s1[1:], s2, s3[1:]) or self.isInterleave(s1, s2[1:], s3[1:])
           else:
               return False
       elif s1[0] == s3[0]:
           return self.isInterleave(s1[1:], s2, s3[1:])
       elif s2[0] == s3[0]:
           return self.isInterleave(s1, s2[1:], s3[1:])
       else:
           return False

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
        if not s1 and not s2 and not s3:
            return True
        if not s1:
            return s2 == s3
        if not s2:
            return s1 == s3
        
        # dp[i][j]    s1 0~i s2 0~j    
        dp = [[False for _ in range(len(s2)+1)] for _ in range(len(s1)+1)]
        dp[0][0] = True
        for i in range(1, len(s1)+1):
            if s1[i-1] == s3[i-1]:
                dp[i][0] = True
            else:
                break
        for i in range(1, len(s2)+1):
            if s2[i-1] == s3[i-1]:
                dp[0][i] = True
            else:
                break
        for i in range(1, len(s1)+1):
            for j in range(1, len(s2)+1):
                if not dp[i][j]:
                    if s1[i-1] == s3[i+j-1] == s2[j-1]:
                        dp[i][j] = dp[i-1][j] or dp[i][j-1]
                    elif s1[i-1] == s3[i+j-1]:
                        dp[i][j] = dp[i-1][j]
                    elif s3[i+j-1] == s2[j-1]:
                        dp[i][j] = dp[i][j-1]
        return dp[len(s1)][len(s2)]