leetcode
leetcode 2851 ~ 2900
多次搜索

多次搜索

难度:

标签:

题目描述

Given a string band an array of smaller strings T, design a method to search b for each small string in T. Output positions of all strings in smalls that appear in big, where positions[i] is all positions of smalls[i].

Example: 

Input: 
big = "mississippi"
smalls = ["is","ppi","hi","sis","i","ssippi"]
Output:  [[1,4],[8],[],[3],[1,4,7,10],[5]]

Note:

  • 0 <= len(big) <= 1000
  • 0 <= len(smalls[i]) <= 1000
  • The total number of characters in smalls will not exceed 100000.
  • No duplicated strings in smalls.
  • All characters are lowercase letters.

代码结果

运行时间: 106 ms, 内存: 35.2 MB

/*
 * 题目思路：
 * 使用 Java Stream API 来实现查找每个 smalls 中的字符串在 big 中出现的所有位置。
 * 我们将遍历 smalls 数组，并使用 Streams 来处理每个字符串的查找过程。
 */

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class SolutionStream {
    public List<List<Integer>> findStringPositions(String big, String[] smalls) {
        return IntStream.range(0, smalls.length)
                        .mapToObj(i -> {
                            String small = smalls[i];
                            List<Integer> positions = new ArrayList<>();
                            int index = big.indexOf(small);
                            while (index != -1) {
                                positions.add(index);
                                index = big.indexOf(small, index + 1);
                            }
                            return positions;
                        })
                        .collect(Collectors.toList());
    }
    public static void main(String[] args) {
        SolutionStream solution = new SolutionStream();
        String big = "mississippi";
        String[] smalls = {"is", "ppi", "hi", "sis", "i", "ssippi"};
        List<List<Integer>> positions = solution.findStringPositions(big, smalls);
        System.out.println(positions);
    }
}

解释

方法:

此题解采用的是暴力匹配的方式来找出small中的字符串在big字符串中的所有出现位置。首先，它检查smalls数组是否为空或只含有一个元素。接着，它创建一个结果列表res来存储每个smalls中字符串的匹配位置。对于smalls中的每个字符串，它首先检查该字符串是否存在于big中。如果存在，它则遍历big字符串，通过比较子字符串big[j:j+len(i)]与smalls中的字符串i，来确定所有匹配的起始位置，并将它们添加到一个临时列表temp中。最后，将temp添加到结果列表res中。

时间复杂度:

O(S*len(big))

空间复杂度:

O(S + len(big))

代码细节讲解

🦆
为什么在解决这个问题时选择使用暴力匹配方法而不是更高效的字符串搜索算法，如KMP、Rabin-Karp或Boyer-Moore？
▷
选择使用暴力匹配方法可能是因为问题的特定上下文或简化实现的考虑。暴力匹配方法代码简单，易于理解和实现，适用于问题规模较小或对性能要求不是非常严格的情况。相比之下，如KMP、Rabin-Karp和Boyer-Moore等算法虽然在最坏情况下提供更好的性能，但它们的实现更复杂，调试和维护更困难。如果big和smalls的大小不是非常大，或者是教学示例的一部分，使用暴力匹配方法可能就足够了。
🦆
在解决方案的实现中，对于每个small字符串检查是否存在于big中（if i in big）似乎是多余的，因为即使字符串存在，你仍需遍历big来查找所有匹配的位置。这种检查的目的是什么？
▷
在实现中进行 `if i in big` 检查的目的是提前过滤掉那些根本不可能在big中找到的small字符串，从而可能减少不必要的遍历。这个检查可以快速确定是否有必要进行后续的详细匹配过程。如果一个small字符串不在big中，那么可以立即跳过对该字符串的进一步搜索，节省计算资源。虽然这看似增加了一次全文扫描的开销，但它实际上能在某些情况下减少整体的计算量，尤其是当smalls中包含多个不可能匹配的字符串时。
🦆
暴力匹配方法在big或smalls中的字符串长度非常大时效率可能会很低，有没有可能通过预处理big来优化搜索过程？例如，使用后缀数组或后缀树？
▷
确实，使用后缀数组或后缀树可以显著优化大规模字符串搜索问题的效率。后缀树和后缀数组允许在预处理阶段花费一定的时间来构建索引，之后可以非常快速地处理多个查询。这种数据结构特别适用于需要频繁搜索多个小字符串（smalls）在一个大字符串（big）中的位置的情况。通过这样的预处理，搜索每个small字符串的时间复杂度可以降低到接近线性，这对于大数据量的应用是非常有益的。因此，对于大规模数据或高性能需求的应用场景，采用这些高效的数据结构是更优的选择。

相关问题

按摩师不用加号的加法