是否找到用于连接的单词列表？

Question

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

示例:输入：“猫”，“狗”，“狗”，“河马”，“老鼠”，“老鼠猫”

输出:猫，狗，猫，老鼠

说明：“猫”可以用“猫”、“狗”、“猫”连接；“狗”可以用“狗”、“猫”、“狗”连接；“鼠猫”可以用“鼠”、“猫”、“狗”、“猫”连接。

我有一个解决方案来返回连接的单词，例如在这种情况下应该是：“猫狗”，“狗猫”，“老鼠猫”。

'''
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]

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

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']

Answer 2

首先，我们根据每个字符串的长度对列表进行排序，这样pend_words函数就可以找到它所检查的单词中最大的单词。

例如:字符串'catscats‘包含'cat’和'cat‘，但是如果它选择’cat‘作为'catscats’的一部分，我们的程序将永远找不到‘cat’。如果'cat‘不在我们的字符串中，程序将在遍历排序的字符串列表时逐渐找到’cat‘。

函数pend_words检索列表中包含其他单词的单词，并删除该单词的那部分。

函数confirm_words检查挂起列表。对于列表中的每个空字符串，这意味着该字符串完全由其他单词组成，因此它会将该单词添加到justified列表中。

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


def pend_words():
    global word,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)

def confirm_words():
    global word
    if word == '':
        for wo in pending:
            if wo not in justfied:
                justfied.append(wo)

l.sort(key=len,reverse=True)
justfied = []

for word in l:

    pending = [] # Create an empty list to pend each potential word (potential because it contains another word)
    modified = False # Before we pend the word, the word hasn't been modified
    pend_words()
    confirm_words()
print(justfied)