Advertisement
Guest User

Untitled

a guest
Feb 18th, 2020
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.67 KB | None | 0 0
  1. class Solution {
  2.     class TrieNode {
  3.         Map<Character, TrieNode> map;
  4.         String word;
  5.         TrieNode() {
  6.             map = new HashMap<>();
  7.             word = null;
  8.         }
  9.        
  10.         void add(String s) {
  11.             if (s == null || s.length() == 0) return;
  12.             add(s, 0);
  13.         }
  14.        
  15.         private void add(String s, int idx) {
  16.             if (idx == s.length()) {
  17.                 word = s;
  18.                 return;
  19.             }
  20.             char c = s.charAt(idx);
  21.             var nextNode = map.computeIfAbsent(c, x -> new TrieNode());
  22.             nextNode.add(s, idx + 1);
  23.         }
  24.        
  25.         private TrieNode next(char c) {
  26.             return map.get(c); // null if there's no item;
  27.         }
  28.     }
  29.    
  30.     public List<String> wordBreak(String s, List<String> wordDict) {
  31.         var trie = new TrieNode();
  32.         for (var w : wordDict) trie.add(w);
  33.         var result = new LinkedList<String>();
  34.         dfs(s, 0, trie, trie, result, new LinkedList<>());
  35.        
  36.         return result;
  37.     }
  38.    
  39.     void dfs(String s, int idx, TrieNode head, TrieNode currentNode, List<String> result, LinkedList<String> acc) {
  40.         if (idx >= s.length()) {
  41.             result.add(String.join(" ", acc));
  42.             return;
  43.         }
  44.            
  45.         var nextTrie = currentNode.next(s.charAt(idx));
  46.         if (nextTrie == null) return;
  47.        
  48.         if (nextTrie.word != null) {
  49.             acc.add(nextTrie.word);
  50.             dfs(s, idx + 1, head, head, result, acc);
  51.             acc.removeLast();
  52.         }
  53.         if (idx + 1 < s.length())
  54.             dfs(s, idx + 1, head, nextTrie, result, acc);
  55.     }
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement