leetcode Interleaving String python 解法

浏览数：33 / 时间：2015年06月08日

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

方案1：DFS

class Solution:
    # @return a boolean
    def isInterleave(self, s1, s2, s3):
        if len(s1)+len(s2) == len(s3):
            return self.DFS(s1,s2,s3)
        else:
            return False
            
    def DFS(self,s1,s2,s3):
        if not (s1 and s2) :
            if s3 == s1+s2:
                return True
            else:
                return False
            
        if s1[0] == s3[0] and self.DFS(s1[1:],s2,s3[1:]):
            return True
        elif s2[0] == s3[0] and self.DFS(s1,s2[1:],s3[1:]):
            return True
        else:
            return False

很不幸的是，超时了

方案2：BFS

import Queue

class Solution:
    # @return a boolean
    def isInterleave(self, s1, s2, s3):
        if len(s1)+len(s2) == len(s3):
            return self.BFS(s1,s2,s3)
        else:
            return False
            
    def BFS(self,s1,s2,s3):
        q = Queue.Queue(len(s3))
        q.put((0,0))
        while(not q.empty()):
            (x,y) = q.get()
            if x==len(s1) or y == len(s2):
                if s3[x+y:] == s1[x:]+s2[y:]:
                    return True
                else:
                    return False
            if s1[x] == s3[x+y]:
                q.put((x+1,y))
            if s2[y] == s3[x+y]:
                q.put((x,y+1))
        
        return False