给定一个单词列表(没有重复项),请编写一个程序,返回给定单词列表中用于连接的所有单词。 串联字定义为在给定数组中完全由至少两个较短字组成的字符串
例如: 输入:[“猫”、“猫”、“猫”、“狗”, “狗狗”、“河马”、“老鼠”、“老鼠狗”]
输出:[“猫”、“狗”、“猫”、“老鼠”]
说明:“猫”可以由“猫”、“狗”和“猫”连接起来; “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]
如何返回用于连接的单词
首先,我们根据每个字符串的长度对列表进行排序,以便pend_words函数可以找到它正在检查的单词中最大的单词
例如:字符串“catscats”同时包含“cat”和“cats”,但如果它选择“cat”作为“catscats”的一部分,我们的程序将永远无法找到“cats”。如果“cat”不在我们的字符串中,程序将在遍历已排序字符串列表时逐渐找到“cat”
函数
pend_words
检索列表中包含其他单词的单词,并删除该部分单词函数
confirm_words
检查挂起列表。对于列表中的每个空字符串,这意味着该字符串完全由其他单词组成,因此它会将该单词添加到justified
列表中我找到了解决办法:
输入:
输出:
相关问题 更多 >
编程相关推荐