50ms java beats 99.88% using Trie


  • 0

    Took me a long time to get AC, the code is a little bit long but the logic is clear, I will add explanation later.

    public class Solution {
        TrieNode root;
        public List<List<Integer>> palindromePairs(String[] words) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            if(words.length<=1) return res;
            root = new TrieNode();
            for(int i=0; i<words.length; i++)
                if(words[i].length()!=0) insert(words[i],i);
            int none = -1;
            for(int i=0; i<words.length; i++){
                if(words[i].length()==0){
                    none = i;
                    continue;
                }
                search(words[i],res,i);
            }
            if(none>=0){
                for(int i=0; i<words.length; i++){
                    if(i!=none&&check(words[i].toCharArray(),0,words[i].length()-1)){
                        res.add(Arrays.asList(i,none));
                        res.add(Arrays.asList(none,i));   
                    }
                }
            }
            return res;
        }
        
        private void search(String s, List<List<Integer>> res, int idx){
            TrieNode tmp = root;
            char[] ss = s.toCharArray();
            for(int i=ss.length-1; i>=0; i--){
                if(tmp.isend){
                    if(check(ss,0,i)){
                        if(tmp.idx!=idx) res.add(Arrays.asList(tmp.idx,idx));
                    }
                }
                if(tmp.children[ss[i]-'a']==null) return;
                tmp = tmp.children[ss[i]-'a'];
            }
            if(tmp.ids.size()>0){
                for(int index:tmp.ids){
                    if(index!=idx) res.add(Arrays.asList(index,idx));
                }
            }
        }
        
        private boolean check(char[] ss, int s, int e){
            while(s<e){
                if(ss[s]!=ss[e]) return false;
                s++;e--;
            }
            return true;
        }
        
        private void insert(String w,int idx){
            TrieNode tmp = root;
            char[] ws = w.toCharArray();
            for(int i=0; i<ws.length; i++){
                if(tmp.children[ws[i]-'a']==null) tmp.children[ws[i]-'a'] = new TrieNode();
                tmp = tmp.children[ws[i]-'a'];
                if(check(ws,i+1,ws.length-1)) tmp.ids.add(idx);
            }
            tmp.isend = true;
            tmp.idx = idx;
        }
        
        class TrieNode{
            TrieNode[] children;
            boolean isend;
            List<Integer> ids;
            int idx;
            public TrieNode(){
                children = new TrieNode[26];
                isend = false;
                idx = 0;
                ids = new ArrayList<Integer>();
            }
        }
    }
    

Log in to reply
 

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