You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
We convert the words into a set to be able to do constant time lookup.
Then we start from the start of the string, iterating over the string and storing the characters.
If we match a word in the set, we recursively retry accumulating from that point on and if it doesn't work we keep accumulating till the end of the word. If we exhaust our options there is no solution.
lru_cache ensures we don't recompute the outcomes for the same value of i, reducing this problem to O(n^2)