Trie solution, but TLE


  • 0
    J
    public class Solution {
        class TrieNode {
            TrieNode[] children;
            boolean isWord;
            public TrieNode() {
                children = new TrieNode[26];
                isWord = false;
            }
        }
        public List<String> wordBreak(String s, Set<String> wordDict) {
            TrieNode root = new TrieNode();
            for (String word : wordDict) {
                input(root, word);
            }
            List<String> ret = new ArrayList<String>();
            List<String> tmp = new LinkedList<String>();
            findBreak(root, s, ret, tmp);
            return ret;
        }
        
        private void findBreak(TrieNode root, String str, List<String> ret, List<String> tmp) {
            if (str.length() == 0) {
                StringBuilder sbl = new StringBuilder();
                for (String s : tmp) {
                    sbl.append(s);
                    sbl.append(' ');
                }
                ret.add(sbl.substring(0, sbl.length() - 1));
                return;
            }
            
            TrieNode cur = root;
            int i = 0;
            while (i < str.length()) {
                cur = cur.children[str.charAt(i) - 'a'];
                if (cur == null) break;
                if (cur.isWord) {
                    tmp.add(str.substring(0, i+1));
                    findBreak(root, str.substring(i+1, str.length()), ret, tmp);
                    tmp.remove(tmp.size() - 1);
                }
                i++;
            }
        }
        
        private void input(TrieNode root, String word) {
            TrieNode cur = root;
            for (int i = 0; i < word.length(); i++) {
                if (cur.children[word.charAt(i) - 'a'] == null)
                    cur.children[word.charAt(i) - 'a'] = new TrieNode();
                cur = cur.children[word.charAt(i) - 'a'];
            }
            cur.isWord = true;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.