文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 暴力超時
    • 2.2 Trie樹

1. 題目

給定一個較長字符串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中沒有重復字符串。 所有出現的字符均為英文小寫字母。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/multi-search-lcci
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

2.1 暴力超時

超時例子

class Solution { public:vector<vector<int>> multiSearch(string big, vector<string>& smalls) {unordered_map<char,vector<int>> m;int i, j, n = smalls.size();bool found;vector<vector<int>> ans(n);for(i = 0; i < big.size(); ++i)m[big[i]].push_back(i);//每個字符開始的位置for(i = 0; i < n; ++i){if(smalls[i].empty())continue;for(auto idx : m[smalls[i][0]])//每個small單詞開始的字符在big里的位置{found = true;if(big.size()-idx < smalls[i].size())break;for(j = 0; j < smalls[i].size(); ++j){ //對big中每個開始的位置開始向后查找smallif(big[idx+j] != smalls[i][j]){found = false;break;}}if(found)ans[i].push_back(idx);}}return ans;} };

2.2 Trie樹

• 將 small 全部插入 trie 樹
• 遍歷 big 的每個位置，并從 big 該位置開始在 trie 中查找

class trie { public:bool isEnd = false;trie* next[26] = {NULL};void insert(string& s){trie *cur = this;for(int i = 0; i < s.size(); ++i){if(!cur->next[s[i]-'a'])cur->next[s[i]-'a'] = new trie();cur = cur->next[s[i]-'a'];}cur->isEnd = true;} }; class Solution { public:vector<vector<int>> multiSearch(string big, vector<string>& smalls) {trie* t = new trie();unordered_map<string,int> m;int i, j, n = smalls.size();bool found;vector<vector<int>> ans(n);for(i = 0; i < n; ++i)m[smalls[i]] = i;for(i = 0; i < n; ++i)t->insert(smalls[i]);string s;trie* cur;for(i = 0; i < big.size(); ++i){s = "";cur = t;for(j = i; j < big.size(); ++j){if(!cur->next[big[j]-'a'])break;s += big[j];cur = cur->next[big[j]-'a'];if(cur->isEnd)ans[m[s]].push_back(i);}}return ans;} };

336 ms 108.7 MB

總結

以上是生活随笔為你收集整理的程序员面试金典 - 面试题 17.17. 多次搜索（Trie树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。