原文链接: https://leetcode-cn.com/problems/multi-search-lcci

英文原文

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.

中文题目

给定一个较长字符串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建trie树，其中每个树节点的sid记录对应的smalls id。
遍历big的所有后缀，并在trie树中查找后缀。对于查找路径上经过的所有有效sid（sid有效值为大于等于0的数），将后缀的起始id加入到sid对应的ans中。

代码

struct TrieNode{
    int sid;
    TrieNode *child[26];
    TrieNode(){
        sid=-1;
        for(int i=0;i<26;++i) child[i]=NULL;
    }
};
class Solution {
private:
    TrieNode *root=new TrieNode();
public:
    void insert(string word,int s){
        int n=word.size();
        TrieNode *cur=root;
        for(int i=0;i<n;++i){
            int cid=word.at(i)-'a';
            if(cur->child[cid]==NULL) cur->child[cid]=new TrieNode();
            cur=cur->child[cid];
        }
        cur->sid=s;
    }
    void search(string word,vector<vector<int>>& ans,int bid){
        int n=word.size();
        TrieNode *cur=root;
        for(int i=0;i<n;++i){
            int cid=word.at(i)-'a';
            if(cur->sid!=-1) ans[cur->sid].push_back(bid);
            if(cur->child[cid]==NULL) return ;
            cur=cur->child[cid];
        }
        if(cur->sid!=-1) ans[cur->sid].push_back(bid);
    }
    vector<vector<int>> multiSearch(string big, vector<string>& smalls) {
        int n=smalls.size(),m=big.size();
        vector<vector<int>> ans(n,vector<int>{});
        for(int i=0;i<n;++i){
            if(smalls[i].size()==0) continue;
            insert(smalls[i],i);
        }
        for(int i=0;i<m;++i){
            string word=big.substr(i,m-i);
            search(word,ans,i);
        }
        return ans;
    }
};

统计信息

通过次数	提交次数	AC比率
8572	19096	44.9%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言