LeeCode 30

本文主要是介绍LeeCode 30，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

LeeCode 30

题目：

思路：

朴素的想法，是创建一个$mp$哈希表记录$words$中所有字符出现的次数，令$n$为$s.size()$,$m$为$words.size()$，$len$为$words[0].size()$。然后枚举$s$中的每一个字符为一个子串的起点，创建第二个$cntHASH$，再遍历子串中的单词，最后检查$cnt$是否等于$mp$，显然该算法的时间复杂度为$O(n\times m\times len)$

根据题目给的数据范围，最坏约为$10^9$，而LeetCode时间限制一秒，一般一秒处理$10^7$左右，所以超时了

Code

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {int n = s.length(), m = words.size(), w = words[0].length();unordered_map<string, int> map;for (const string& word : words) {map[word]++;}vector<int> ans;for (int i = 0; i + m * w <= n; i++) {unordered_map<string, int> cur;string sub = s.substr(i, m * w);bool valid = true;for (int j = 0; j < sub.length(); j += w) {string item = sub.substr(j, w);if (map.find(item) == map.end()) {valid = false;break;}cur[item]++;}if (valid && cur == map) {ans.push_back(i);}}return ans;}
};

优化：

每个子串的起点是不可避免的需要枚举的，但是我们检查子串是否合法的的过程中，窗口每向前移动一次，我们就要遍历一次子串，与此同时我们发现，当前检查完的$cnt$哈希表可以通过删除左侧的单词，添加右侧的的单词，得到窗口向前直接滑一个单词的长度后的$cnt$的状态，所以我们把$n\mathrm{mod}len$将起点分为len类（只有$\mathrm{mod}len$才能遍历所有的合法的起点，因为每次要向前滑$len$，$i+k\times len(0\le i\le len-1)$遍历每个与它相同余数的起点。

AcCode

class Solution
{
public:vector<int> findSubstring(string s, vector<string> &words){unordered_map<string, int> mp;for (auto x : words){mp[x]++;}vector<int> ans;int n = s.size();int m = words.size();int len = words[0].size();for (int i = 0; i < len; i++){unordered_map<string, int> cnt;for (int j = i; j + len <= n; j += len){// j,i为起始位置，len为单词长度string tmp = s.substr(j, len);cnt[tmp]++;// 当有一个完整的窗口时，滑动窗口，每次移动一个单词的长度if (j >= i + m * len){string tmp = s.substr(j - m * len, len);// 删除最左边的单词,cnt[tmp]>=1,不会出现负数cnt[tmp]--;if (cnt[tmp] == 0){cnt.erase(tmp);}}//j是最后一个单词的第一个字符if (j >= i + (m - 1) * len){if (cnt == mp){ans.push_back(j - (m - 1) * len);}}}}return ans;}
};

这篇关于LeeCode 30的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---