trie的应用

[pan-qin]

https://leetcode-cn.com/problems/multi-search-lcci/
注意如何create trie, insert, search only use a global trienode
注意字符串字串内层循环j从i开始

Idea:

create a trie for smalls. Iterate through all substring of big. If the substring is found in the trie, save the ID of the trieNode. ID is the corresponding position of each small in the smalls array.

Complexity:

Time: O(N^2) N is the length of big
Space: O(k* n) n is the avg length of small words, k is the size of character set

class Solution {
    TrieNode root = new TrieNode();
    public int[][] multiSearch(String big, String[] smalls) {          
        int m=smalls.length;
        for(int i=0;i<m;i++) {
            insert(smalls[i],i);
        }
        //use an array of arraylist to store results       
        List<Integer>[] res = new List[m];
        for(int i=0;i<m;i++) {
            res[i] = new ArrayList<Integer>();
        }
        //iterate over all substring of big, if the substring is in the trie, save the index
        int n = big.length();    
        for(int i=0;i<n;i++) {
            TrieNode curr=root;
            for(int j=i;j<n;j++) {
                char c = big.charAt(j);
                if(curr.children[c-'a']==null)
                    break;
                curr=curr.children[c-'a'];
                if(curr.isWord==true) {
                    res[curr.ID].add(i);
                }
            }

        }
        //convert res to 2d array
        int[][] ret = new int[m][];
        for(int i=0;i<m;i++) {
            ret[i]=new int[res[i].size()];
            for(int j=0;j<res[i].size();j++) {
                ret[i][j]=res[i].get(j);
            }
        }
        return ret;

    }     
        //insert new word into trie
        private void insert(String word, int index) {
            TrieNode curr = root;
            for(int i=0;i<word.length();i++) {
                char c = word.charAt(i);
                if(curr.children[c-'a']==null) {
                    curr.children[c-'a'] = new TrieNode();
                }
                curr=curr.children[c-'a'];
            }
            curr.ID=index;
            curr.isWord=true;
        }

        private class TrieNode {
            TrieNode[] children;
            int ID; //store the index of smalls
            boolean isWord;

            public TrieNode() {
                children = new TrieNode[26];
                isWord = false;
                ID=-1;
            }
        }
    
}

Originally posted by @panda-qin in leetcode-pp/91alg-5-daily-check#94 (comment)