Leetcode 472.连接词
2024-08-29 10:37:29
连接词
给定一个不含重复单词的列表,编写一个程序,返回给定单词列表中所有的连接词。
连接词的定义为:一个字符串完全是由至少两个给定数组中的单词组成的。
示例:
输入: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
输出: ["catsdogcats","dogcatsdog","ratcatdogcat"]
解释: "catsdogcats"由"cats", "dog" 和 "cats"组成;
"dogcatsdog"由"dog", "cats"和"dog"组成;
"ratcatdogcat"由"rat", "cat", "dog"和"cat"组成。
说明:
- 给定数组的元素总数不超过 10000。
- 给定数组中元素的长度总和不超过 600000。
- 所有输入字符串只包含小写字母。
- 不需要考虑答案输出的顺序。
思路是:
对于words中的每个单词w,我们定义一个数组dp[n+1],如果dp[i] == true,则表示w.substr(0, i)可以由words中的已有单词连接而成。那么状态转移方程就是:dp[i] = {dp[j] && w.substr(j + 1, i - j) is in words},其中j < i。最终检查dp[n]是否为true,如果是则将其加入结果集中。为了加速对words中的单词的查找,我们用一个哈希表来保存各个单词。这样时间复杂度可以降低到O(n * m^2),其中n是words中的单词的个数,m是每个单词的平均长度(或者最大长度?)。
import java.util.*; class Solution {
public List<String> findAllConcatenatedWordsInADict(String[] words) {
Set<String> set=new HashSet<String>();
for(int i=0;i<words.length;i++){
set.add(words[i]);
}
List<String> res=new ArrayList<String>();
for(String word:words){
int n=word.length();
boolean[] dp=new boolean[n+1];
Arrays.fill(dp,false);
dp[0]=true;
for(int i=0;i<n;i++){
if(!dp[i]) continue;
for(int j=i+1;j<=n;j++){
if(j-i<n && set.contains(word.substring(i,j))){
dp[j]=true;
}
}
if(dp[n]){
res.add(word);
break;
}
}
}
return res;
}
}
最新文章
- Sql Server系列:分区表操作
- nmq消息队列解析
- HDFS文件和HIVE表的一些操作
- Bootstrap3.0学习第十八轮(JavaScript插件——下拉菜单)
- JavaScript 经常忽略的 7 个基础知识点
- c#中using System.Runtime.Serialization.Json;不能引用
- swfObject 使用说明
- javascript中的闭包。
- The type xxx cannot be resolved. It is indirectly referenced from required .class files
- 短信验证倒计时60s
- PHP做好防盗链的基本思想 防盗链的设置方法
- java--map容器的hashcode和equals
- Node.js 入门(2)
- Duanxx的C++得知:计算位数
- nodejs 模拟form表单上传文件
- Qlik报表开发见解
- DB2开发系列之一——基本语法
- Httpclient post请求
- idea 导eclipse项目
- tarjan——cogs 1298 通讯问题
热门文章
- BaseAdapter获取View之三重境界
- oracle 、server和my sql 语法区别
- CF Gym 100637G 	\#TheDress (水)
- groff - groff 文档排版系统前端
- python基础一 day15 内置函数
- lca(最近公共祖先(离线))
- nodejs 静态资源服务与接口代理跨域
- 【转】再谈 最速下降法/梯度法/Steepest Descent
- 学习笔记(二):使用 TensorFlow 的起始步骤(First Steps with TensorFlow)
- C++图书馆管理系统项目中部分功能代码实现(书籍推荐)