0

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.

Improve this question
2
  • The code looks correct, except perhaps you'd have problems if the recursion goes too deep. But debugging problems on stackoverflow require a specific problem and reproduction of the problem in the question. Commented Aug 27, 2017 at 6:55
  • Try to switch to pypy. Though the timeout for pypy is much lower than for python, in some cases you won't exceed it. Commented Aug 27, 2017 at 8:08

1 Answer 1

Reset to default
1

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

11 Comments

can you elaborate more as I am doing very similar to that in my recursive approach?
@user3053970 Added short example on how to do the matching without recursion. You need to modify it though so that you can print the passwords in case there's a match,
@monster You're correct but that was intentionally left out since the question was asking hint, not a full solution.
oh sorry. deleted my comment so no worries:)
@user3053970: Added explanation why the code provided in the question is so slow compared to example in the answer.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.