LeetCode 题解

积跬步，至千里。

多次搜索

分类：程序员面试金典题解 标签： 字典树 字符串 发布于：2020-05-20 ID：17.17

题目描述

来源于 https://leetcode-cn.com/

给定一个较长字符串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中没有重复字符串。
  • 所有出现的字符均为英文小写字母。

解法一：暴力搜索

class Solution {
public:
    vector<vector<int>> multiSearch(string big, vector<string>& smalls) {
        vector<vector<int>> ret;
        for(string& s: smalls){
            vector<int> positions;
            if(s.empty()){
                ret.push_back(::move(positions));
                continue;
            }
            int start = 0;
            int i = big.find(s, start);
            
            while(i != string::npos){
                positions.push_back(i);
                start = i + 1;
                i = big.find(s, start);
            }
            ret.push_back(::move(positions));
        }
        return ret;
    }
};

解法二：Trie

把所有短单词都存储在 Trie 中。然后使用 big[i:] 去 Trie 树中寻找 big[i:] 的前缀。