contains clas emp dfs urn key 分析 超时 字典
题目:
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.
Return all such possible sentences.
For example, given
s =
,dict =
- "catsanddog"
.
- ["cat", "cats", "and", "sand", "dog"]
A solution is
.
- ["cats and dog", "cat sand dog"]
题意及分析:给出一个字符串和一个字典,求能用字典里的单词将字符串分割的所有可能。使用深度遍历的方法,每次判断字符串是否以字典中的单词为开头,如果是开头,继续判断剩余的字符串;如果最后字符串长度为0,那么就找到了能分割字符串的单词组成。这里用一个hashMap保存中间结果,否则会超时。
代码:
- class Solution {
- public List < String > wordBreak(String s, List < String > wordDict) {
- return DFS(s, wordDict, new HashMap < String, LinkedList < String >> ());
- }
- List < String > DFS(String s, List < String > wordDict, HashMap < String, LinkedList < String >> map) {
- if (map.containsKey(s)) return map.get(s);
- LinkedList < String > res = new LinkedList < >();
- if (s.length() == 0) {
- res.add("");
- return res;
- }
- for (String word: wordDict) {
- if (s.startsWith(word)) {
- List < String > subList = DFS(s.substring(word.length()), wordDict, map);
- for (String sub: subList) {
- res.add(word + (sub.isEmpty() ? "": " ") + sub);
- }
- }
- }
- map.put(s, res);
- return res;
- }
- }
[LeetCode] 140. Word Break II java
来源: http://www.bubuko.com/infodetail-2355747.html