This problem simply restated is this: given a bunch of strings and a target string, what all combinations from the given string can combine together to form target string with and without repetition.
e.g.
strings: we do what we must because we can
target: wedowhatwemustbecausewecan
output: we do what we must because we can
Approach I took is to remove every longer word from the target until target becomes empty. If targets becomes empty then just return the output. If longer words doesn't lead to a solution then try with shorter words and so on. I am also using memoization to make sure that if the target is already tried then just return, same as backtracking with memoization.
This apporach passed all the testcases except 2, where I am getting timeout.
def recursions(word_map, paswd, output, remember):
flag = 0
if len(paswd) == 0:
return 1
if paswd in remember:
return flag
for char in paswd:
for word in (word_map[char] if char in word_map else []):
if paswd.startswith(word):
output.append(word + " ")
if recursions(word_map, paswd[len(word):], output, remember):
return 1
output.pop()
remember[paswd] = 1
return flag
Please help in providing a hint. Complete solution is here.
You could try dynamic programming approach where you mark the ending locations of each password. Start by trying every password at the beginning of the longer string. If it fits there mark down the ending position in the longer string. You could then repeat the same process for every location in longer string where previous location is marked as ending position.
Hope this helps you getting started, I've intentionally left out some of the information required for full solution so let me know in comments if you're still stuck.
EDIT Here's a short example on what I'm talking about. It doesn't allow you to reconstruct the solution but it shows how to do the matching without recursion:
passwords = ['foo', 'bar']
login = 'foobar'
ends_here = [False] * len(login)
for i in range(len(ends_here)):
# Match password at the beginning or if password match
# ended to previous index
if i == 0 or ends_here[i - 1]:
for pw in passwords:
if login.find(pw, i, i + len(pw)) != -1:
ends_here[i + len(pw) - 1] = True
print(ends_here)
print('We can match whole login attempt:', ends_here[-1])
Output:
[False, False, True, False, False, True]
We can match whole login attempt: True
EDIT Took a closer look at the code provided in the question. The issue is on the line where matched strings are filtered by the characters contained in the target: for char in paswd:. Instead of doing filtering for every character in the target string the filtering should be done for every unique character: for char in set(paswd):. Fix that and solution runs much faster but would probably be even faster if there wouldn't be that kind of filtering at all since the maximum number of shorter strings is 10.