面试题 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中没有重复字符串。
所有出现的字符均为英文小写字母。

题解

public int[][] multiSearch(String big, String[] smalls) {
    int lenBig = big.length(), lenSmall = smalls.length;
    // 字符前缀缓存
    Map<Character, Set<Integer>> cache = new HashMap<>(26);
    for (int i = 0; i < lenBig; i++) {
        cache.merge(big.charAt(i), new HashSet<>(Collections.singleton(i)), (o, n) -> {
            o.addAll(n);
            return o;
        });
    }

    Function<String, int[]> getPositions = s -> {
        Set<Integer> indices;
        // 字符串为空或者不存在大字符串中不存在以短字符串开头的
        if (s.isEmpty() || (indices = cache.getOrDefault(s.charAt(0), new HashSet<>())).isEmpty()) {
            return new int[0];
        }

        int sLen = s.length();
        return
            indices.stream()
                // 是否存在大字符串中
                .filter(it -> lenBig - it >= sLen && big.substring(it, it + sLen).equals(s))
                .mapToInt(Integer::intValue)
                .sorted()
                .toArray();
    };

    // 按照小单词依次遍历
    int[][] result = new int[lenSmall][];
    for (int i = 0; i < lenSmall; i++) {
        result[i] = getPositions.apply(smalls[i]);
    }
    return result;
}