1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
Set<String> dictSet = new HashSet<>(wordDict);
List<String> ans = new ArrayList<>();
helper(ans, s, new StringBuilder(), dictSet, 0);
return ans;
}
private void helper(List<String> ans, String s, StringBuilder curr, Set<String> dictSet, int ptr) {
if (ptr == s.length()) {
ans.add(curr.toString().trim());
return;
}
for (int i = ptr + 1; i <= s.length(); i++) {
String currString = s.substring(ptr, i);
if (dictSet.contains(currString)) {
curr.append(currString).append(' ');
helper(ans, s, curr, dictSet, i);
curr.delete(curr.length() - (currString.length() + 1), curr.length());
}
}
}
}
|
backtrack就完事儿了.
时间复杂度: O(2^n) 比如aaaaaaaaaaaa, dict是[a, aa, aaa, aaaa, aaaaa]
空间复杂度: O(n) 每一个栈都代表截取了原string的一部分. 因此最多每个截取都是1个char.
