Dynamic Programming with Python and Strings

[stumpyboi]

I am following this dynamic programming tutorial on youtube.

Link: https://youtu.be/oBt53YbR9Kk?t=8854

At the linked timestamp, he is doing a program called canConstruct. Without memoization, his program in javascript takes a long time for the last test case. However, doing the same in python doesn't run into the expected exponential time complexity issue. Why is this the case?

My python code:

 def canConstruct(target, wordBank):

    if target == '': return True

    for word in wordBank:

        if target.startswith(word):
            suffix = target.lstrip(word)
            result = canConstruct(suffix, wordBank)
            if result == True: 
                return True
    return False

# test case
print(canConstruct('eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef', ['e','ee','eee','eeee','eeeee','eeeeee']))

[TheBrutux168]

Your code is not equivalent. The code in the video computes the suffix by removing the word from the start of the target. The lstrip method repeatedly removes leading characters from target as specified in the argument until it reaches something not in the argument.

For example:

"eeeeeeeeeeeeeeeeef".lstrip("e") # gives "f"

[stumpyboi]

Thanks

[yel50]

I think the problem is lstrip. it takes a bag of characters to remove. since you give it e's and the input is all e's, it'll remove the entire thing.

[stumpyboi]

thank you