LeetCode刷题【面试题 17.17】多次搜索

给定一个较长字符串big和一个包含较短字符串的数组smalls，设计一个方法，根据smalls中的每一个较短字符串，对big进行搜索。输出smalls中的字符串在big里出现的所有位置positions，其中positions[i]为smalls[i]出现的所有位置。

示例：

输入：
big = "mississippi"
smalls = ["is","ppi","hi","sis","i","ssippi"]
输出： [[1,4],[8],[],[3],[1,4,7,10],[5]]

提示：

• 0 <= len(big) <= 1000
• 0 <= len(smalls[i]) <= 1000
• smalls的总字符数不会超过 100000。
• 你可以认为smalls中没有重复字符串。
• 所有出现的字符均为英文小写字母。

smalls数组构建字典树

1. 把smalls数组构建字典树
2. 把big数组从第i位开始到结尾的子序列拿到字典树上匹配，i从0开始分别求解，直到结束
3. 因为匹配的时候需要知道当前字典树上字符串结束节点是哪个字符的，所以字典树的节点需要额外记录下各自归属与smalls数组中对应字符串的下标
4. 在树上匹配的过程中，但凡匹配到了一个结束字符，就在结果数组的对应这个字符串下标的子数组中插入一个当前匹配的big字符串子序列的开始下标

代码

class Solution {
    public int[][] multiSearch(String big, String[] smalls) {
        Trie trie = new Trie();
        trie.smallsCount = smalls.length;
        trie.insert(smalls);
        return trie.search(big);
    }


    public class Trie{

        Node tree;
        int smallsCount = 0;

        public Trie(){
            tree = new Node();
        }

        void insert(String[] strArr){
            for (int idx = 0; idx < strArr.length; idx++) {
                Node cur = tree;
                String str = strArr[idx];
                int i = -1;
                while (++i < str.length()){
                    int child = str.charAt(i)-'a';
                    if (cur.children[child] == null){
                        cur.children[child] = new Node();
                    }
                    cur = cur.children[child];
                }
                cur.flag = true;
                cur.smallIndex = idx;
            }
        }

        int[][] search(String str){
            int[][] res = new int[smallsCount][];
            List<List<Integer>> list = new ArrayList<>();
            for (int i = 0; i < smallsCount; i++) {
                list.add(new ArrayList<>());
            }

            for (int i = 0; i < str.length(); i++) {
                String subStr = str.substring(i);
                Node cur = tree;
                int idx = -1;
                while (cur != null && ++idx < subStr.length()){
                    char c = subStr.charAt(idx);
                    if (cur.children[c-'a'] != null){
                        cur = cur.children[c-'a'];
                        if (cur.flag){
                            list.get(cur.smallIndex).add(i);
                        }
                    }else{
                        break;
                    }
                }
            }
            for (int i = 0; i < list.size(); i++) {
                res[i] = list.get(i).stream().mapToInt(Integer::intValue).toArray();
            }
            return res;
        }




        class Node{
            boolean flag = false;
            Node[] children;
            int smallIndex = -1;
            public Node(){
                children = new Node[26];
            }
        }
    }
}