DFS+DP+Trie beats 81%


  • 0
    Z

    Use a trie to optimize the prefix matching process.

    public class Solution {
        class Trie{
            class TrieNode{
                TrieNode[] children = new TrieNode[26];
                boolean hasValue;
            }
            TrieNode root;
            public Trie(List<String> words){
                root = new TrieNode();
                Iterator<String> itr = words.iterator();
                while(itr.hasNext()){
                    insert(itr.next());
                }
            }
            public void insert(String s){
                TrieNode cur = root;
                for(int i=0;i<s.length();i++){
                    int index = s.charAt(i) - 'a';
                    if(cur.children[index]==null)cur.children[index] = new TrieNode();
                    cur = cur.children[index];
                }
                cur.hasValue = true;
            }
            public List<String>findNextPrefix(String s){
                List<String> res = new LinkedList<>();
                TrieNode cur = root;
                for(int i=0;i<s.length();i++){
                    int index = s.charAt(i) - 'a';
                    if(cur.children[index]==null)break;
                    if(cur.children[index].hasValue)res.add(s.substring(0,i+1));
                    cur = cur.children[index];
                }
                return res;
            }
        }
        public List<String> wordBreak(String s, List<String> wordDict) {
            HashMap<String, List<String>>memo = new HashMap<>();
            Trie trie = new Trie(wordDict);
            return  helper(s,trie,memo);
        }
        public List<String> helper(String s, Trie trie,HashMap<String, List<String>>memo){
            List<String> thisTmp = new LinkedList<>();
            if(memo.containsKey(s)){return memo.get(s);}
            if(s.length()==0){thisTmp.add("");return thisTmp;}
            List<String> words = trie.findNextPrefix(s);
            for(String next: words){
                if(!s.startsWith(next))continue;
                List<String> tmp = helper(s.substring(next.length()),trie,memo);
                for(String sub: tmp){
                    thisTmp.add(next+(sub.isEmpty()?"":" ")+sub);
                }
            }
            memo.put(s,thisTmp);
            return thisTmp;
        }
    }
    

Log in to reply
 

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