首页 > 其他 > 详细

Leetcode 472.连接词

时间:2019-01-17 01:10:21      阅读:87      评论:0      收藏:0      [点我收藏+]

标签:div   复杂度   哈希   res   i+1   pre   -i   宋体   nat   

连接词

给定一个不含重复单词的列表,编写一个程序,返回给定单词列表中所有的连接词。

连接词的定义为:一个字符串完全是由至少两个给定数组中的单词组成的。

示例:

输入: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]

 

输出: ["catsdogcats","dogcatsdog","ratcatdogcat"]

 

解释: "catsdogcats"由"cats", "dog" 和 "cats"组成;

"dogcatsdog"由"dog", "cats"和"dog"组成;

"ratcatdogcat"由"rat", "cat", "dog"和"cat"组成。

说明:

  1. 给定数组的元素总数不超过 10000。
  2. 给定数组中元素的长度总和不超过 600000。
  3. 所有输入字符串只包含小写字母。
  4. 不需要考虑答案输出的顺序。

 

 

思路是:

对于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是每个单词的平均长度(或者最大长度?)。

 

 1 import java.util.*;
 2 
 3 class Solution {
 4     public List<String> findAllConcatenatedWordsInADict(String[] words) {
 5         Set<String> set=new HashSet<String>();
 6         for(int i=0;i<words.length;i++){
 7             set.add(words[i]);
 8         }
 9         List<String> res=new ArrayList<String>();
10         for(String word:words){
11             int n=word.length();
12             boolean[] dp=new boolean[n+1];
13             Arrays.fill(dp,false);
14             dp[0]=true;
15             for(int i=0;i<n;i++){
16                 if(!dp[i]) continue;
17                 for(int j=i+1;j<=n;j++){
18                     if(j-i<n && set.contains(word.substring(i,j))){
19                         dp[j]=true;
20                     }
21                 }
22                 if(dp[n]){
23                     res.add(word);
24                     break;
25                 }
26             }
27         }
28         return res;
29     }
30 }

 

Leetcode 472.连接词

标签:div   复杂度   哈希   res   i+1   pre   -i   宋体   nat   

原文:https://www.cnblogs.com/kexinxin/p/10280230.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 designnerd.net 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号