5ms Java solution using tries


  • 1
    Z
    public class Solution {
        public boolean wordBreak(String s, Set<String> wordDict) {
            trie dict = new trie();
            for(String a:wordDict){
                trie at = dict;
                for(int i=0;i<a.length();i++){
                    if(at.branches[a.charAt(i)-'a']==null)
                        at.branches[a.charAt(i)-'a']=new trie();
                    at = at.branches[a.charAt(i)-'a'];
                }
                at.end=true;
            }
           // System.out.println(dict);
            usedStarts=new boolean[s.length()+1];
            return recurse(s,dict,dict,0);
        }
        static boolean[]usedStarts;
        static boolean recurse(String a, trie dict, trie at, int ati){
           // System.out.println(a+" "+at+" "+ati);
            if(at==null)
                return false;
            if(ati==a.length())
                return at.end;
            if(at.end&&!usedStarts[ati]){
                usedStarts[ati]=true;
                if(recurse(a,dict,dict,ati))
                    return true;
            }
            return recurse(a,dict,at.branches[a.charAt(ati)-'a'],ati+1);
        }
        static class trie{
            public trie[]branches;
            public boolean end;
            public trie(){
                branches=new trie[26];
                end=false;
            }
            public String toString(){
                return "["+end+" "+Arrays.toString(branches)+"]";
            }
        }
    }

Log in to reply
 

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