Java with Trie 18ms


  • 0
    J

    public class Solution {
    public class Trie{
    Trie[] children;
    public Trie(){
    children = new Trie[27];
    }

        public void add(String word, int index){
            if(index==word.length()){
                if(children[26]==null) children[26] = new Trie();
            }else{
                char c = word.charAt(index);
                if(children[(int)(c-'a')]==null) children[(int)(c-'a')] = new Trie();
                children[(int)(c-'a')].add(word, index+1);
            }
        }
    }
    
    public int findLUSlength(String[] strs) {
        Map<Integer, List<String>> map = new HashMap<Integer, List<String>>();
        for(int i=0;i<strs.length;i++){
            int len = strs[i].length();
            if(!map.containsKey(len)) map.put(len, new ArrayList<String>());
            map.get(len).add(strs[i]);
        }
        List<Integer> lens = new ArrayList<Integer>(map.keySet());
        Collections.sort(lens);
        Trie root = new Trie();
        for(int i=lens.size()-1;i>=0;i--){
            int len = lens.get(i);
            List<String> list = map.get(len);
            Map<String, Integer> map1 = new HashMap<String,Integer>();
            for(int j=0;j<list.size();j++){
                String str = list.get(j);
                if(!map1.containsKey(str)) map1.put(str,0);
                map1.put(str,map1.get(str)+1);
            }
            Iterator<String> ite = map1.keySet().iterator();
            while(ite.hasNext()){
                String str = ite.next();
                if(map1.get(str)==1&&!isSubSequence(root, str, 0)) return len;
                root.add(str, 0);
            }
        }
        return -1;
    }
    
    public boolean isSubSequence(Trie root, String str, int index){
        if(index==str.length()) return true;
        if(root==null) return false;
        char c = str.charAt(index);
        if(root.children[(int)(c-'a')]!=null){
            return isSubSequence(root.children[(int)(c-'a')], str, index+1);
        }else{
            for(int i=0;i<26;i++){
                if(isSubSequence(root.children[i], str, index)) return true;
            }
            return false;
        }
    }
    

    }


Log in to reply
 

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