Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- class TrieNode {
- Map<Character, TrieNode> map;
- String word;
- TrieNode() {
- map = new HashMap<>();
- word = null;
- }
- void add(String s) {
- if (s == null || s.length() == 0) return;
- add(s, 0);
- }
- private void add(String s, int idx) {
- if (idx == s.length()) {
- word = s;
- return;
- }
- char c = s.charAt(idx);
- var nextNode = map.computeIfAbsent(c, x -> new TrieNode());
- nextNode.add(s, idx + 1);
- }
- private TrieNode next(char c) {
- return map.get(c); // null if there's no item;
- }
- }
- public List<String> wordBreak(String s, List<String> wordDict) {
- var trie = new TrieNode();
- for (var w : wordDict) trie.add(w);
- var result = new LinkedList<String>();
- dfs(s, 0, trie, trie, result, new LinkedList<>());
- return result;
- }
- void dfs(String s, int idx, TrieNode head, TrieNode currentNode, List<String> result, LinkedList<String> acc) {
- if (idx >= s.length()) {
- result.add(String.join(" ", acc));
- return;
- }
- var nextTrie = currentNode.next(s.charAt(idx));
- if (nextTrie == null) return;
- if (nextTrie.word != null) {
- acc.add(nextTrie.word);
- dfs(s, idx + 1, head, head, result, acc);
- acc.removeLast();
- }
- if (idx + 1 < s.length())
- dfs(s, idx + 1, head, nextTrie, result, acc);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement