SHARE
TWEET

Untitled

a guest Aug 22nd, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2.     public List<String> wordBreak(String s, List<String> wordDict) {
  3.         return wordBreak(s, wordDict, 0, new LinkedList<String>(), new HashSet<>());
  4.     }
  5.    
  6.     public List<String> wordBreak(String s, List<String> wordDict, int offset, LinkedList<String> history, HashSet<Integer> deadEnds) {
  7.         if (offset == s.length()) {
  8.             List<String> result = new LinkedList<>();
  9.             result.add(String.join(" ", history));
  10.             return result;
  11.         }
  12.        
  13.         List<String> possibleCombinations = new LinkedList<>();
  14.        
  15.         if (deadEnds.contains(offset))
  16.             return possibleCombinations;
  17.        
  18.         for(String w : wordDict) {
  19.             if (!s.startsWith(w, offset))
  20.                 continue;
  21.             history.addLast(w);
  22.             possibleCombinations.addAll(wordBreak(s, wordDict, offset + w.length(), history, deadEnds));
  23.             history.removeLast();
  24.         }
  25.        
  26.         if (possibleCombinations.size() == 0)
  27.             deadEnds.add(offset);
  28.         return possibleCombinations;
  29.     }
  30. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top