【leetcode】472. Concatenated Words
2024-10-07 14:41:50
题目如下:
Given a list of words (without duplicates), please write a program that returns all concatenated words in the given list of words.
A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.
Example:
Input: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"] Output: ["catsdogcats","dogcatsdog","ratcatdogcat"] Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats";
"dogcatsdog" can be concatenated by "dog", "cats" and "dog";
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".Note:
- The number of elements of the given array will not exceed
10,000
- The length sum of elements in the given array will not exceed
600,000
.- All the input string will only include lower case letters.
- The returned elements order does not matter.
解题思路:我的方法是Input按单词的长度升序排序后存入字典树中,因为Input中单词不重复,所有较长的单词肯定是由比其短的单词拼接而成的。每个单词在存入字典树的时候,同时做前缀匹配,并保存匹配的结果,接下来再对这些结果递归做前缀匹配,直到无法匹配或者完全匹配为止。如果有其中任意一个结果满足完全匹配,则表示这个单词可以由其他的单词拼接而成。
代码如下:
class TreeNode(object):
def __init__(self, x):
self.val = x
self.childDic = {}
self.hasWord = False class Trie(object):
dic = {}
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = TreeNode(None)
self.dic = {} def divide(self, word,flag):
substr = []
current = self.root
path = ''
for i in word:
path += i
if i not in current.childDic:
current.childDic[i] = TreeNode(i)
current = current.childDic[i]
if current.hasWord:
substr.append(word[len(path):])
self.dic[path] = 1
if flag:
self.dic[word] = 1
current.hasWord = True
return substr
def isExist(self,w):
return w in self.dic class Solution(object):
def findAllConcatenatedWordsInADict(self, words):
"""
:type words: List[str]
:rtype: List[str]
"""
words.sort(cmp=lambda x1,x2:len(x1) - len(x2))
t = Trie()
res = []
for w in words:
queue = t.divide(w,True)
while len(queue) > 0:
item = queue.pop(0)
if t.isExist(item):
res.append(w)
#t.dic[w] = 1
break
else:
queue += t.divide(item,False)
return res
最新文章
- html基础起航
- Asp.net Web API 返回Json对象的两种方式
- PHP中九大缓存技术总结
- Android Mvc 实现
- Collection Operators
- C/C++中的可变参函数
- ORACLE数据库常用查询二
- opencv学习之旅_绘制跟踪轨迹
- 修改linux共享内存大小
- Ubuntu 14.04安装地里编码软件Nominatim过程
- 关于BOM 的详细介绍
- Linq to sharepoint
- Linux(CentOS7)下如何配置多个Tomcat容器
- Eclipse中快捷键Ctrl + Alt + 向上箭头 或者 Ctrl + Alt + 向下箭头与Windows冲突
- SSL通信-忽略证书认证错误
- CSS/Xpath 选择器 第几个子节点/父节点/兄弟节点
- [LintCode] 77. Longest common subsequences_ Medium tag: Dynamic Programming
- Oracle DataBase 编码格式
- HTTP协议中长连接与短连接的区别
- pacbio bax.h5文件处理及ccs计算