Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public List<String> wordBreak(String s, List<String> wordDict) {
- return wordBreak(s, wordDict, 0, new LinkedList<String>(), new HashSet<>());
- }
- public List<String> wordBreak(String s, List<String> wordDict, int offset, LinkedList<String> history, HashSet<Integer> deadEnds) {
- if (offset == s.length()) {
- List<String> result = new LinkedList<>();
- result.add(String.join(" ", history));
- return result;
- }
- List<String> possibleCombinations = new LinkedList<>();
- if (deadEnds.contains(offset))
- return possibleCombinations;
- for(String w : wordDict) {
- if (!s.startsWith(w, offset))
- continue;
- history.addLast(w);
- possibleCombinations.addAll(wordBreak(s, wordDict, offset + w.length(), history, deadEnds));
- history.removeLast();
- }
- if (possibleCombinations.size() == 0)
- deadEnds.add(offset);
- return possibleCombinations;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement