生活随笔
收集整理的這篇文章主要介紹了
140. Word Break II
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
文章目錄
1 題目理解
140與130的區別是，當字符串可分的時候，要求返回具體的分割字符串。
2 回溯+記憶化
對于字符串s，如果前面一部分是單詞列表中的詞，則拆分出這個單詞，右邊的繼續分割。
分割過程中，對起始下標i，已經分割過的，用map緩存。
使用字典樹也可以加快搜索速度。
class Solution {private Trie trie
;private List<String> result
;public List<String> wordBreak(String s
, List<String> wordDict
) {int n
= s
.length();trie
= new Trie();trie
.initWord(wordDict
);result
= new ArrayList<String>();dfs(s
,0);return cache
.get(0);}private Map<Integer,List<String>> cache
= new HashMap<Integer,List<String>>();private void dfs(String s
, int i
){if(i
>=s
.length()){return;}if(cache
.get(i
)!=null) return;List<String> r
= new ArrayList<String>();for(int x
= i
+1;x
<=s
.length();x
++){String left
= s
.substring(i
,x
);if(trie
.find(left
)){dfs(s
,x
);if(cache
.get(x
)!=null){for(String right
: cache
.get(x
)){r
.add(left
+" "+right
);}}else{r
.add(left
);}}}cache
.put(i
,r
);}
}
class Trie{private TrieNode root
= new TrieNode('/');public void initWord(List<String> wordDict
){for (String word
: wordDict
){addWord(word
);}}public boolean find(String word
){TrieNode node
= root
;for(int i
=0;i
<word
.length();i
++){int index
= word
.charAt(i
) - 'a';if(node
.children
[index
]==null){return false;}node
= node
.children
[index
];}return node
.end
;}private void addWord(String word
) {TrieNode node
= root
;for(int i
=0;i
<word
.length();i
++){int index
= word
.charAt(i
) - 'a';if(node
.children
[index
]==null){node
.children
[index
] = new TrieNode(word
.charAt(i
));}node
= node
.children
[index
];}node
.end
= true;}class TrieNode{TrieNode[] children
= new TrieNode[26];boolean end
;private char data
;public TrieNode(char data
){this.data
= data
;}}
}
補充：也可以在139的基礎上做。在找到0到i可以分割的時候，記錄下分割方式。當然這種方法也可以加上Trie樹。
class Solution {public List<String> wordBreak(String s
, List<String> wordDict
) {Map<Integer,List<String>> resultMap
= new HashMap<Integer,List<String>>();int n
= s
.length();boolean[] dp
= new boolean[n
+1];dp
[0] = true;for(int i
=1;i
<=n
;i
++){resultMap
.put(i
, new ArrayList<String>());for(int j
=0;j
<i
;j
++){if(dp
[j
]==true && wordDict
.contains(s
.substring(j
,i
))){dp
[i
]=true;if(j
==0){resultMap
.get(i
).add(s
.substring(j
,i
));}else{for(String pre
:resultMap
.get(j
)){resultMap
.get(i
).add(pre
+" "+s
.substring(j
,i
));}} }}}return resultMap
.get(n
);}
}
總結
以上是生活随笔為你收集整理的140. Word Break II的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
