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++){
|
07 |
if ( dp[i] == null ) continue ;
|
08 |
for (String word:dict){
|
09 |
int len = word.length();
|
11 |
if (end > s.length()) continue ;
|
12 |
if (s.substring(i,end).equals(word)){
|
14 |
dp[end] = new ArrayList<String>();
|
21 |
List<String> ans = new LinkedList<String>();
|
22 |
if (dp[s.length()] == null ) return ans;
|
23 |
ArrayList<String> tmp = new ArrayList<String>();
|
24 |
dfsStringList(dp,s.length(),ans, tmp);
|
28 |
public static void dfsStringList(List<String> dp[], int end,List<String> res, ArrayList<String> tmp){
|
30 |
String ans = tmp.get(tmp.size()- 1 );
|
31 |
for ( int i=tmp.size()- 2 ; i>= 0 ; i--)
|
32 |
ans += ( " " + tmp.get(i) );
|
36 |
for (String str:dp[end]){
|
38 |
dfsStringList(dp,end-str.length(), res, tmp);
|
39 |
tmp.remove(tmp.size()- 1 );
|
当然也有其他的解法,这个只是参考,效率其实还可以。
分享到:
相关推荐
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...
<HeaderStyle HorizontalAlign="Center"></HeaderStyle> <ItemStyle CssClass="dxgv"></ItemStyle> ... myDataGrid_d.Attributes.Add("style", "word-break:keep-all;word-wrap:normal");
复制代码代码如下:”c1″>safjaskflasjfklsajfklasjflksajflksjflkasfdsafdsfksafj</div><div class=c1>This is all English. This is all English. This is all English.</div><div class=c1>全是中文的情况。...
word-break:break-all和word-wrap:break-word都是能使其容器如DIV的内容自动换行。 它们的区别就在于: 1,word-break:break-all 例如div宽200px,它的内容就会到200px自动换行,如果该行末端有个英文单词很长...
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 ...
object.style.wordBreak="keep-all" 值 描述 normal 使用浏览器默认的换行规则。 break-all 允许在单词内换行。 keep-all 只能在半角空格或连字符处换行。 兼容性: 举个栗子: CSS Co
兼容 IE 和 FF 的换行 CSS 推荐样式 最好的方式是 word-wrap:break-word; overflow:hidden; 而不是 word-wrap:break-word; word-break:break-all; 也不是 word-wrap:break-word; overflow:auto; 在 IE 下没有任何...
word-wrap用来控制换行 两种取值: (1)normal (2)break-word(此值用来强制换行,内容将在边界内换行,中文没有任何问题,英文语句也没问题。但是对于长串的英文,就不起作用。) word-break用来控制断词 三种取值...
word-wrap:normal | break-word; (内容换行) normal:默认的属性值.(允许内容顶开指定的容器边界). break-word:内容将在边界内换行(不截断英文单词换行,截断英文单词下面的属性才具备这个功能。) word-break:no
第 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
前端开源库-breakwordbreakword,获取字符索引,在该索引之后,变量“word”必须在给定变量“length”(占宽字符数)的情况下断开。
在table中加入 style="WORD-WRAP: normal;TABLE-LAYOUT: fixed;word-break:normal" 总结如下.
本文是CSS属性探秘系列的第一篇,详细介绍了word-break与word-wrap的异同与示例分析,非常简单实用,有需要的朋友可以参考下
现在的浏览器对文本的换行处理还是比较合理的,当文字超过容器宽度时会自动换行,那么它是怎么自动换行的呢?本文将带你详细探讨,感兴趣的你可不要错过了,希望本文对你学习换行方面知识有所帮助
leetcode 苹果断字 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,确定 s 是否可以被分割成一个或多个字典单词的空格分隔序列。 笔记: 字典中的同一个词可能会在切分中重复使用多次。...word. E