python代码的时间复杂度，用于查找可以由列表中的其他单词组成的最长单词（后续）(Time complexity of python code for finding the longest word that can be made of other words in the list (follow-up))

 我知道一个类似的问题已经被提出并解决了（ python代码的时间复杂度，用于查找可以由列表中的其他单词组成的最长单词 ），但我有一个后续问题。 
 
 我有以下问题， 
 
# Given a list of words, find the longest word made of other words in the list.
# Example: [cat, banana, dog, nana, walk, walker, dogwalker]
# Result: dogwalker
 
 我在Python 3中有以下实现： 
 
def find_longest_word(list_words):
    list_words = sorted(list_words, key=lambda x:len(x))[::-1]
    for elem in list_words:
        set_remaining = set(list_words) - set([elem])
        if find_if_composite(elem, set_remaining, {}):
            return elem
    return None

def find_if_composite(s, set_):
    n = len(s)
    if len(set_) == 0 or n == 0:
        return False
    if s in set_:
        return True
    for i in range(1, n+1):
        this_s = s[:i]
        if this_s in set_:
            if find_if_composite(s[i:], set_): # assuming that I can reuse the string
                return True
    return False
 
 我们从前面的答案中知道这个代码在O（N！）中运行，其中N是字符串的大小（如果我是正确的）。 
 
 我的问题是：有没有办法改善时间复杂度（例如，使用memoization）？ 如果没有，为什么？ 如果有，怎么样？ 我尝试了以下代码，但似乎它在递归调用期间从未命中过备忘录。 
 
def find_if_composite_memo(s, set_, memo):
    n = len(s)
    if len(set_) == 0 or n == 0:
        return False
    if s in memo:
        return memo[s]
    if s in set_:
        return True
    for i in range(1, n+1):
        this_s = s[:i]
        if this_s in set_:
            if find_if_composite_memo(s[i:], set_, memo):
                memo[s] = True
                memo[s[i:]] = True
                return True
    memo[s] = False
    return False
 
 要测试，请使用 
 
b = ["cat", "banana", "dog", "nana", "walk", "walker", "dogwalker", "dogwalkerbanana"]
print(find_longest_word(b))

I know that a similar question has already been asked and solved (Time complexity of python code for finding the longest word that can be made of other words in the list), but I have a follow-up question. 
 
I have the following problem, 
 
# Given a list of words, find the longest word made of other words in the list.
# Example: [cat, banana, dog, nana, walk, walker, dogwalker]
# Result: dogwalker
 
I have the following implementation in Python 3:
 
def find_longest_word(list_words):
    list_words = sorted(list_words, key=lambda x:len(x))[::-1]
    for elem in list_words:
        set_remaining = set(list_words) - set([elem])
        if find_if_composite(elem, set_remaining, {}):
            return elem
    return None

def find_if_composite(s, set_):
    n = len(s)
    if len(set_) == 0 or n == 0:
        return False
    if s in set_:
        return True
    for i in range(1, n+1):
        this_s = s[:i]
        if this_s in set_:
            if find_if_composite(s[i:], set_): # assuming that I can reuse the string
                return True
    return False
 
We know from the previous answer that this code runs in O(N!) where N is the size of the string (if I am correct).
 
My question is: is there any way to improve the time complexity (e.g., using memoization)? If not, why? If yes, how? I tried the following code but it seems like it never hits the memo during recursive calls. 
 
def find_if_composite_memo(s, set_, memo):
    n = len(s)
    if len(set_) == 0 or n == 0:
        return False
    if s in memo:
        return memo[s]
    if s in set_:
        return True
    for i in range(1, n+1):
        this_s = s[:i]
        if this_s in set_:
            if find_if_composite_memo(s[i:], set_, memo):
                memo[s] = True
                memo[s[i:]] = True
                return True
    memo[s] = False
    return False
 
To test, use
 
b = ["cat", "banana", "dog", "nana", "walk", "walker", "dogwalker", "dogwalkerbanana"]
print(find_longest_word(b))

原文：https://stackoverflow.com/questions/35463014