`
chriszeng87
  • 浏览: 713819 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Word Break II

阅读更多

转自:http://www.acmerblog.com/word-break-ii-6128.html?utm_source=tuicool

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

请参考LeetCode-Word Break 查看该题的第一个版本:判断是否可分词成功。但是这一题,不仅要判断是否可以分词,还要找到所有的分词结果。

第一题是用dp[i]表示 字符串s[0....i-1]是否可以分词成功。

为了记录是怎么分词的,我们可以用dp[i]表示 字符串s[0.....i-1]的最后一个分词word,则s[0.....i-1]的倒数第二个分词即为dp[o....i-word.length()-1]。但这种方法只能记录一种分词方法,因此有必要把 dp[i] 定义 List<String>,这样就可以表示多种分词方法,最后使用DFS搜索,找到所有的分词方法。

例如对于上面的例子:  s.length()=10, 则 dp[10] = {“cat”}, dp[7]={“and”,”sand”}, dp[4]={“cats”}, dp[3]={“cat”}, dp[0]={}, 其它的都为null。

dfs搜索的时,可以从后向前,也可以从前向后,只要保证最终结果的顺序即可。下面是用的从后向前搜索。

01 public class Solution {
02     public static List<String> wordBreak(String s, Set<String> dict) {
03         List<String> dp[] = new ArrayList[s.length()+1];
04         dp[0] = new ArrayList<String>();
05         for(int i=0; i<s.length(); i++){
06             //i是开始位置
07             if( dp[i] == null continue//前面的部分必须是可以匹配的
08             for(String word:dict){
09                 int len = word.length();
10                 int end = i+len;
11                 if(end > s.length()) continue;
12                 if(s.substring(i,end).equals(word)){
13                     if(dp[end] == null){
14                         dp[end] = new ArrayList<String>();
15                     }
16                     dp[end].add(word);//记录上一个位置
17                 }
18             }
19         }
20  
21         List<String> ans = new LinkedList<String>();
22         if(dp[s.length()] == nullreturn ans;
23         ArrayList<String> tmp = new ArrayList<String>();
24         dfsStringList(dp,s.length(),ans, tmp);
25         return ans;
26     }
27  
28     public static void dfsStringList(List<String> dp[],int end,List<String> res, ArrayList<String> tmp){
29         if(end <= 0){
30             String ans = tmp.get(tmp.size()-1);
31             for(int i=tmp.size()-2; i>=0; i--)
32                 ans += (" " + tmp.get(i) );
33             res.add(ans);
34             return;
35         }
36         for(String str:dp[end]){
37             tmp.add(str);
38             dfsStringList(dp,end-str.length(), res, tmp);
39             tmp.remove(tmp.size()-1);
40         }
41     }
42 }

当然也有其他的解法,这个只是参考,效率其实还可以。

分享到:
评论

相关推荐

    LintCode 582: Word Break II

    Word Break II Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences. Example Example 1...

    webfrom-列表文本内容自动换行 word-break-keep-all;word-wrap-n.pdf

    &lt;HeaderStyle HorizontalAlign="Center"&gt;&lt;/HeaderStyle&gt; &lt;ItemStyle CssClass="dxgv"&gt;&lt;/ItemStyle&gt; ... myDataGrid_d.Attributes.Add("style", "word-break:keep-all;word-wrap:normal");

    css中强制换行word-break、word-wrap、white-space区别实例说明

    复制代码代码如下:”c1″&gt;safjaskflasjfklsajfklasjflksajflksjflkasfdsafdsfksafj&lt;/div&gt;&lt;div class=c1&gt;This is all English. This is all English. This is all English.&lt;/div&gt;&lt;div class=c1&gt;全是中文的情况。...

    word-break:break-all和word-wrap:break-word区别总结

    word-break:break-all和word-wrap:break-word都是能使其容器如DIV的内容自动换行。 它们的区别就在于: 1,word-break:break-all 例如div宽200px,它的内容就会到200px自动换行,如果该行末端有个英文单词很长...

    cpp-算法精粹

    Word Break II Dungeon Game House Robber House Robber II House Robber III Range Sum Query - Immutable Range Sum Query 2D - Immutable 图 Clone Graph 位操作 Reverse Bits Repeated DNA Sequences Number of ...

    浅析word-break work-wrap的区别

    object.style.wordBreak="keep-all"   值 描述 normal 使用浏览器默认的换行规则。 break-all 允许在单词内换行。 keep-all 只能在半角空格或连字符处换行。 兼容性: 举个栗子: CSS Co

    CSS word-wrap同word-break的区别

    兼容 IE 和 FF 的换行 CSS 推荐样式 最好的方式是 word-wrap:break-word; overflow:hidden; 而不是 word-wrap:break-word; word-break:break-all; 也不是 word-wrap:break-word; overflow:auto; 在 IE 下没有任何...

    css 英文换行 css(word-wrap/break)使纯英文数字自动换行

    word-wrap用来控制换行 两种取值: (1)normal (2)break-word(此值用来强制换行,内容将在边界内换行,中文没有任何问题,英文语句也没问题。但是对于长串的英文,就不起作用。) word-break用来控制断词 三种取值...

    CSS的Word_break、Word_Wrap的区别及应用

    word-wrap:normal | break-word; (内容换行) normal:默认的属性值.(允许内容顶开指定的容器边界). break-word:内容将在边界内换行(不截断英文单词换行,截断英文单词下面的属性才具备这个功能。) word-break:no

    leetcode338-coding_notebook:编码_笔记本

    第 338 章概括 [(雅虎)4。...问题/数组和字符串/140.word_break_ii.md) [151. 反转字符串中的单词](Leetcode Problems/Array and String/151.reverse_words_in_a_string.md) [167. Two Sum 2 - In

    前端开源库-breakword

    前端开源库-breakwordbreakword,获取字符索引,在该索引之后,变量“word”必须在给定变量“length”(占宽字符数)的情况下断开。

    css word-break word-wrap 前台显示自动换行

    在table中加入 style="WORD-WRAP: normal;TABLE-LAYOUT: fixed;word-break:normal" 总结如下.

    CSS属性探秘系列(一):word-break与word-wrap

    本文是CSS属性探秘系列的第一篇,详细介绍了word-break与word-wrap的异同与示例分析,非常简单实用,有需要的朋友可以参考下

    word-wrap与word-break 属性的概述及浏览器默认处理

    现在的浏览器对文本的换行处理还是比较合理的,当文字超过容器宽度时会自动换行,那么它是怎么自动换行的呢?本文将带你详细探讨,感兴趣的你可不要错过了,希望本文对你学习换行方面知识有所帮助

    leetcode苹果-word-break:断字

    leetcode 苹果断字 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,确定 s 是否可以被分割成一个或多个字典单词的空格分隔序列。 笔记: 字典中的同一个词可能会在切分中重复使用多次。...word. E

Global site tag (gtag.js) - Google Analytics