python - 查找用于连接的单词列表？

Question

给定一个单词列表（没有重复），请编写一个程序，返回给定单词列表中用于连接的所有单词。连接的单词被定义为一个字符串，该字符串完全由给定数组中的至少两个较短的单词组成。

示例：输入：["cat","cats","catsdogcats","dog", "dogcatsdog","hippopotamuses","rat","ratcatdogcat"]

输出：["cats","dog","cats", "rat"]

解释：“catsdogcats”可以由“cats”、“dog”和“cats”串联；"dogcatsdog" 可以由 "dog"、"cats" 和 "dog" 连接；“ratcatdogcat”可以由“rat”、“cat”、“dog”和“cat”连接。

我有返回连接单词的解决方案，例如在这种情况下应该是：["catsdogcats","dogcatsdog","ratcatdogcat"]

'''
If a word can be Concatenated from shorter words, then word[:i] and word[i:] must also be Concatenated from shorter words.
Build results of word from results of word[:i] and word[i:]
Iterate i from range(1, len(word)) to avoid a word is Concatenated from itself.
Use memorization to avoid repeat calculation.
Time: O(n*l)
Space: O(n)
'''
class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        mem = {}
        words_set = set(words)
        return [w for w in words if self.check(w, words_set, mem)]

    def check(self, word, word_set, mem):
        if word in mem:
            return mem[word]
        mem[word] = False
        for i in range(1, len(word)):
            if word[:i] in word_set and (word[i:] in word_set or self.check(word[i:], word_set, mem)):
                mem[word] = True
                break
        return mem[word]

我如何返回用于连接的单词？

标签： pythonpython-3.xrecursiondynamic-programming

Answer 1

我找到了解决方案：

输入：

l = ['cats','cat','dogcats','dog','catpig','pigs','pigspigs','goatdog','goat','rabbit']

l.sort(key=len,reverse=True) # Sort the list from most letters to least
justfied = [] # List of justified strings
for word in l:
    pending = [] # List of pending strings
    modified = False # Check whether a string have been modified
    for _ in range(len(word)):
        for wor in l:
            if wor in word and not(wor == word and modified==False):
                word = word.replace(wor,'',1)
                modified = True
                pending.append(wor)
    if word == '':
        for wo in pending:
            if wo not in justfied:
                justfied.append(wo)
print(justfied)

输出：

['pigs', 'cats', 'dog', 'goat']