链接: 472. 连接词
难度:困难
给你一个 不含重复 单词的字符串数组 words
,请你找出并返回 words
中的所有 连接词 。
连接词 定义为:一个完全由给定数组中的至少两个较短单词组成的字符串。
示例 1:
输入:words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"] 输出:["catsdogcats","dogcatsdog","ratcatdogcat"] 解释:"catsdogcats" 由 "cats", "dog" 和 "cats" 组成; "dogcatsdog" 由 "dog", "cats" 和 "dog" 组成; "ratcatdogcat" 由 "rat", "cat", "dog" 和 "cat" 组成。
示例 2:
输入:words = ["cat","dog","catdog"] 输出:["catdog"]
提示:
1 <= words.length <= 104
0 <= words[i].length <= 30
words[i]
仅由小写字母组成0 <= sum(words[i].length) <= 105
words
建立字典树。find_split_count(s)
,这个方法的作用是用words中的单词恰好
拼接s,寻找最多能把word切几段。words
中每个单词执行一遍这个函数,返回值>=2的单词就是答案。words
中出现了,那么只要s2也在words
中出现,那么这个s就是满足题意的字符串;s2也可本身不用出现,只需要它能用words
中多个字符串拼起来即可。find_split_count(s2)
。class TrieNode: def __init__(self,cnt=0): self.cnt = cnt self.next = [None]*26 self.is_end = False def insert(self, word: str) -> None: cur = self for c in word: i = ord(c)-ord('a') if not cur.next[i] : # 没有这个字符 cur.next[i] = TrieNode() cur = cur.next[i] cur.cnt += 1 cur.is_end = True def find_split_count(self,word,start,n): if start == n: return 0 cur = self m = 0 for i in range(start,n): c = word[i] idx = ord(c) - ord('a') if not cur.next[idx]: return 0 cur = cur.next[idx] if cur.is_end: m = self.find_split_count(word,i+1,n)+1 if m >= 2: return m return m if cur.is_end else 0 class Solution: def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]: trie = TrieNode() n = len(words) for word in words: trie.insert(word) # word='nuqhmfj' # print(trie.find_split_count(word,0,len(word))) return [word for word in words if trie.find_split_count(word,0,len(word)) >=2]
链接: 面试题 17.15. 最长单词
面试题 17.15. 最长单词
难度:中等
给定一组单词words
,编写一个程序,找出其中的最长单词,且该单词由这组单词中的其他单词组合而成。若有多个长度相同的结果,返回其中字典序最小的一项,若没有符合要求的单词则返回空字符串。
示例:
输入: ["cat","banana","dog","nana","walk","walker","dogwalker"] 输出: "dogwalker" 解释: "dogwalker"可由"dog"和"walker"组成。
提示:
0 <= len(words) <= 200
1 <= len(words[i]) <= 100
class TrieNode: def __init__(self, cnt=0): self.cnt = cnt self.next = [None] * 26 self.is_end = False def insert(self, word: str) -> None: cur = self for c in word: i = ord(c) - ord('a') if not cur.next[i]: # 没有这个字符 cur.next[i] = TrieNode() cur = cur.next[i] cur.cnt += 1 cur.is_end = True def find_split_count(self, word, start, n): if start == n: return 0 cur = self m = 0 for i in range(start, n): idx = ord(word[i]) - ord('a') if not cur.next[idx]: return 0 cur = cur.next[idx] if cur.is_end: m = self.find_split_count(word, i + 1, n) + 1 if m >= 2: # print(word[start:i + 1], word[i + 1:], m) return m return m if cur.is_end else 0 class Solution: def longestWord(self, words: List[str]) -> str: ans = '' m = 0 trie = TrieNode() for word in words: trie.insert(word) for word in words: n = len(word) if trie.find_split_count(word,0,n)>=2: if n > m : m = n ans = word elif n == m and word < ans: ans = word return ans
人生苦短,我用Python!