本文主要是介绍LeetCode 30 Substring with Concatenation of All Words，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给出字符串s和许多等长(len)单词w，找出所有s中的满足子串为w中所有单词的一种组合的位置。
思路：
因为w中的单词要满足的是组合而不是排列，因此用“区间[L,R]中包含单词的计数”来维护比较合适。
一是满足了组合对顺序的不要求，二是方便处理重复的单词。
首先可以统计一下，w中各种单词个数。如果s的长度为size(w) * len的子串单词计数与w相同，则找到一个答案。
接着去s中找到所有w中单词出现的位置，因为单词等长，所以可以开一个长度为size(s)的数组A，A[i]记录着从i位置开始长度为len的s的子串对应哪个单词。
然后枚举区间[L,R]判断是否为答案。可以这样做，L起始位置枚举[0, len - 1]，初始R与L相同表示空队列，接着R端每次入队一个len长度的s的子串，如果队列长度超过size(w) * len则队首出队，再检查队列中字符串的计数，如果与w相同，则记录答案。这里还有一个维护技巧，为了避免对应单词的计数的比较，可以维护队列中单词的计数一定小于w中计数，方法就是一旦队列中某单词x计数多了，那么L不断右移len个单位，直到x计数满足条件为止。
最后将答案返回。
代码：
class Solution {
public:vector<int> findSubstring(string s, vector <string> &words) {vector<int> ans;ans.clear();if (words.size() == 0) {return ans;}map<string, int> hash;hash.clear();for (int i = 0, idx = 0; i < words.size(); ++i) {if (!hash.count(words[i])) {hash[words[i]] = idx++;}}int *cnt = new int[hash.size()];memset(cnt, 0, sizeof(int) * hash.size());for (int i = 0, idx = 0; i < words.size(); ++i) {++cnt[hash[words[i]]];}int *start = new int[s.size()];memset(start, -1, sizeof(int) * s.size());for (auto i = hash.begin(); i != hash.end(); ++i) {for (int idx = -1; idx + 1 < s.size();) {idx = s.find(i->first, idx + 1);if (idx != -1) {start[idx] = i->second;} else {break;}}}int len = words[0].size();for (int i = 0; i < len; ++i) {int tmpcnt = 0;int k = i;for (int j = i; j + len <= s.size(); j += len) {if ((j - k) / len == words.size()) {if (start[k] != -1) {--tmpcnt;++cnt[start[k]];}k += len;}if (start[j] != -1) {--cnt[start[j]];++tmpcnt;while (cnt[start[j]] < 0) {if (start[k] != -1) {--tmpcnt;++cnt[start[k]];}k += len;}if (tmpcnt == words.size()) {ans.push_back(j - (tmpcnt - 1) * len);}}}for (; k + len <= s.size(); k += len) {if (start[k] != -1) {++cnt[start[k]];}}}sort(ans.begin(), ans.end());return ans;}
};这篇关于LeetCode 30 Substring with Concatenation of All Words的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
