查找用于连接的单词列表?

2024-03-29 08:19:25 发布

您现在位置:Python中文网/ 问答频道 /正文

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

例如: 输入:[“猫”、“猫”、“猫”、“狗”, “狗狗”、“河马”、“老鼠”、“老鼠狗”]

输出:[“猫”、“狗”、“猫”、“老鼠”]

说明:“猫”可以由“猫”、“狗”和“猫”连接起来; “dogcatsdog”可以由“狗”、“猫”和“狗”连接; “ratcatdogcat”可以由“rat”、“cat”、“dog”和“cat”连接

我有返回连接词的解决方案,例如,在本例中,应为: [“猫猫”、“狗猫狗”、“老鼠猫”]

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

如何返回用于连接的单词


Tags: andinfromself列表returnifcheck
2条回答

首先,我们根据每个字符串的长度对列表进行排序,以便pend_words函数可以找到它正在检查的单词中最大的单词

例如:字符串“catscats”同时包含“cat”和“cats”,但如果它选择“cat”作为“catscats”的一部分,我们的程序将永远无法找到“cats”。如果“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)

我找到了解决办法:

输入:

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

相关问题 更多 >