https://leetcode.com/problems/interleaving-string/
Can anybody please tell me...WHY???
I submitted the same code using two different dictionaries...
1st : Collections.defaultdict---> It gave me TLE
2nd : {} i.e. dict() ---> It got submitted very easily
- USING DEFAULTDICT
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
l1 = len(s1)
l2 = len(s2)
l3 = len(s3)
if l3!=l1+l2:
return False
if l1==0:
return True
dp = defaultdict(lambda:1)
def find(i,j,k):
if i==l1 and j==l2 and k==l3:
return True
if k==l3:
return False
if dp[(i,j,k)] == 1:
dp[(i,j,k)] = False
if (i < l1 and s3[k]==s1[i] and find(i+1,j,k+1)):
dp[(i,j,k)] = True
if (j < l2 and s3[k]==s2[j] and find(i,j+1,k+1)):
dp[(i,j,k)] = True
return dp[(i,j,k)]
return find(0,0,0)- USING DICT()
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
l1 = len(s1)
l2 = len(s2)
l3 = len(s3)
if l3!=l1+l2:
return False
if l1==0:
return True
dp = {}
def find(i,j,k):
if i==l1 and j==l2 and k==l3:
return True
if k==l3:
return False
if (i,j,k) not in dp:
dp[(i,j,k)] = False
if (i < l1 and s3[k]==s1[i] and find(i+1,j,k+1)):
dp[(i,j,k)] = True
if (j < l2 and s3[k]==s2[j] and find(i,j+1,k+1)):
dp[(i,j,k)] = True
return dp[(i,j,k)]
return find(0,0,0)Comments (1)