python - 如何从这个递归函数中获得正确的结果？

Question

在下一个函数中，我试图返回构造单词的方式数量：target使用单词的部分列表：word_bank。

我很难弄清楚为什么它没有返回正确的答案：

def count_construct(target, word_bank):

    if target == '':
        return 1

    total_count = 0

    for prefix in word_bank:
        if target.startswith(prefix):
            new_target = target.replace(prefix, '')
            num_ways = count_construct(new_target, word_bank)
            total_count += num_ways

    return total_count

print(count_construct('enterapotentpot', ['a', 'p', 'ent', 'enter', 'ot', 'o', 't']))  # answer: 4

正确答案应该是4，但此时它返回1。

对于下一个测试用例，它工作得很好：

print(count_construct('purple', ['purp', 'p', 'ur', 'le', 'purpl']))                    # answer: 2
print(count_construct('abcdef', ['ab', 'abc', 'cd', 'def', 'abcd']))                    # answer: 1
print(count_construct('skateboard', ['bo', 'rd', 'ate', 't', 'ska', 'sk', 'boar']))     # answer: 0

如果有人帮助我弄清楚我做错了什么，我将不胜感激。

谢谢你的帮助。

标签： pythonpython-3.x

Answer 1

@MisterMiyagi 请在评论中添加答案，我在这里添加它以解决问题：

new_target = target.replace(prefix, '')替换所有出现的target. 改为使用new_target = target[len(prefix):]。