Java with Trie 18ms

  • 0

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

        public void add(String word, int index){
                if(children[26]==null) children[26] = new Trie();
                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>());
        List<Integer> lens = new ArrayList<Integer>(map.keySet());
        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);
            Iterator<String> ite = map1.keySet().iterator();
                String str =;
                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);
            return isSubSequence(root.children[(int)(c-'a')], str, index+1);
            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.