A nice question I got in interview that Im trying to find a better solutions to it.
So you get a target string and a dictionary of strings.
You need to return an array of string arrays that shows all the ways you can build the target if possible.
target = "aabcd"
words = ["a", "b", "c", "bc", "bcd", "d"]
res = findWays(target, words)the result above will be:
[
["a", "a", "b", "c", "d"],
["a", "a", "bc", "d"],
["a", "a", "bcd"],
]The only solution I had in mind is a recursion but its slowwwww
memo = {}
def fbrec(target, words):
if target == "":
return [[]]
if target in memo:
return memo[target]
results = []
for i in range(0 ,len(target)):
first = target[0:i+1]
sec = target[i+1:]
if first in words:
res = fbrec(sec, words)
if res:
for item in res:
results.append([first] + item)
memo[target] = results
return resultsComments (2)