目录

• 题目
• 思路
  • 代码
  • 复杂度分析

题目

面试题 17.17. 多次搜索

思路

• 将所有的短单词构建成一个前缀树，同时也要讲短单词的位置记录下来，因为要的结果也是有序的
• 然后查找的时候，用长字符串来匹配：将长字符串的每一个字符作为开头，截取他的子串，将其子串在前缀树中进行查找，匹配的话就将结果加入到结果集中即可

代码

class Solution {
    public int[][] multiSearch(String big, String[] smalls) {
        // 其中一个为null直接返回null
        if (big == null || smalls == null) {
            return null;
        }
        // 初始化前缀树
        Trie trie = new Trie();
        // 将字串构建成一颗前缀树
        trie.insertWords(smalls);
        // 查询字串再big中的位置
        return trie.searchBigWord(big);
    }
}

/**
* 前缀树
**/
class Trie {
    // 记录子串位置
    private int position;
    // 记录子串个数
    private int wordSize;
    // 当前字符的孩子
    private Trie[] children;
    // 是否到达末尾，即用来判断是否是一个子串
    private boolean end;

    public Trie() {
        position = 0;
        children = new Trie[26];
    }

    public void insertWords(String[] smallWords) {
        // 获取子串个数
        wordSize = smallWords.length;

        for (int i = 0; i < smallWords.length; i++) {
            // for遍历将每一个子串插入道前缀树种，共同构建一颗前缀树，同时还要记录字串的位置position，因为到时候输出的结果就是要按照对应子串的位置输出
            insertPer(smallWords[i], i);
        }
    }

    /**
    * 将字符串添加道前缀树中
    */
    public void insertPer(String word, int position) {
        // 先获取前缀树根节点，根节点的孩子是用来指向第一个字符的，然而其中的wordSize、存储固定唯一的数据子串长度
        Trie node = this;

        for (int i = 0; i < word.length(); i++) {
            if (node.children[word.charAt(i) - 'a'] == null) {
                node.children[word.charAt(i) - 'a'] = new Trie();
            }
            node = node.children[word.charAt(i) - 'a'];
        }
        node.position = position;
        // 子串添加到前缀树中成功
        node.end = true;
    }

    public int[][] searchBigWord(String bigWord) {
        // 创建一个零食存储结果的数组，要用ArrayList，因为LinkedList不能初始容量大小
        List<List<Integer>> temp = new ArrayList<>(this.wordSize);

        // 初始化内部的子数组，也是用ArrayList
        for (int i = 0; i < wordSize; i++) {
            temp.add(new ArrayList<Integer>());
        }

        // 将字符串的每个字符都当作第一个字符
        for (int i = 0; i < bigWord.length(); i++) {
            // 获取子串
            String subWord = bigWord.substring(i);
            // 获取根节点
            Trie node = this;
            for (int j = 0; j < subWord.length(); j++) {
                // 只要为null，就说明不是当前字符串子串
                if (node.children[subWord.charAt(j) - 'a'] == null) {
                    break;
                }
                node = node.children[subWord.charAt(j) - 'a'];
                // 判断是不是一个子串，是的话添加索引道temp中
                if (node.end) {
                    temp.get(node.position).add(i);
                }
            }
        }

        // 将temp重新映射为普通的二维数组返回结果
        int[][] res = new int[temp.size()][];
        for (int i = 0; i < temp.size(); i++) {
            List<Integer> subList = temp.get(i);
            res[i] = new int[subList.size()];
            for (int j = 0; j < subList.size(); j++) {
                res[i][j] = subList.get(j);
            }
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：
  • 建树：\(O(M*N)\)，其中 M 为每个单词的平均长度， N 为短单词的个数
  • 搜索：\(O(S*N)\)，其中 S 为单词的长度，N 为每次长单词的命中次数
• 空间复杂度：
  • 建树：\(O(M*N)\)，其中 M 为字符集中所占的字符个数，N 为短单词的个数
  • 搜索：\(O(N)\)，其中 N 为命中的个数