i am following dynamic programming tutorial. It is a code for checking if a subset of strings is able to form the main string
A side from memoization, It is mentioned that the following if
statement helps fasten the calculation, that if a single branch of calculation is true, it will return True and not calculating the rest of the branch.
if canConstruct(remainder_string,words,memo):
memo[target_string] = True
However, I have randomly modified the code without the if function and still get the same results and same "speed"
When I print the remainder_string during the loop. both the code looks the same.
Please help explain is there any actual difference between Code A and Code B?
# Code A
def canConstruct(target_string,words,memo=None):
if memo == None: memo = dict()
if target_string in memo:
return memo[target_string]
if target_string == "": return True
for word in words:
if target_string.startswith(word):
remainder_string = target_string[len(word):]
print(remainder_string)
if canConstruct(remainder_string,words,memo): # This is added to make calculation faster
memo[target_string] = True
return memo[target_string]
memo[target_string] = False
return False
print(canConstruct('ccccccccccccccccccccccccccccccf',['c','cc','cccc','ccccc','ccccccccc','ccccccccccccccccc','d']))
# Code B
def canConstruct(target_string,words,memo=None):
if memo == None: memo = dict()
if target_string in memo:
return memo[target_string]
if target_string == "": return True
for word in words:
if target_string.startswith(word):
remainder_string = target_string[len(word):]
print(remainder_string)
memo[target_string] = canConstruct(remainder_string,words)
return memo[target_string]
return False
print(canConstruct('ccccccccccccccccccccccccccccccf',['c','cc','cccc','ccccc','ccccccccc','ccccccccccccccccc','d']))
Aucun commentaire:
Enregistrer un commentaire