LeetCode题目30：串联所有单词的子串
原题描述
+
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
示例 1：
输入：
s = "barfoothefoobarman",
words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。示例 2：
输入：
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
输出：[]原题链接：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words
思路解析
+
注意到题干中“不需要考虑words中单词串联的顺序”，这种“只关心是否出现过，及出现的次数，而不管顺序”的匹配模式，应该条件反射般地想到hashmap。
现在的问题是，我们把words中的所有单词都存入hashmap，我们命名为A，并统计数目之后，如何使用它进行匹配？在s中一边滑动滑窗一边在A中匹配，貌似是一个比较有前途的思路。
因为words中的所有单词都是相等长度，尚且记录为 ，所以我们每次取 个字符作为判断的粒度。
如果某个子串完全符合题目要求，那么理论上这个子串是能够完美映射到A中的，无论是命中情况，还是每个单词的统计次数。如果我们再为当前子串创建一个临时hashmap，暂且称之为B，那么当扫描完该子串后，A和B应该完全一样。
基本思路就是这样。总结一下，使用滑窗，并利用hashmap判断无序字串的匹配，是本题的重点。
其实判断可以提前剪枝。当出现下面两种情况之一时，就以提前退出，继续探索一个滑窗了。
- 某个单词w，在A中没有出现过；
- 某个单词w虽然在A中出现过，但是出现的次数比A中的统计数多。
复杂度分析
+
- 时间复杂度：
- 空间复杂度： ， 为words个数
算法过程
+
1. 初始化words的hashmap
2. 开始滑窗判断，边判断边记录临时hashmap
3. 两个hashmap完全相等。说明已经找到了解
4. 最后的位置上其实也没必要判断了，因为组成子串的单词个数不满足要求。如果硬要判断，是如下这个过程。
C++参考代码
+
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
if (!words.size()) return {};
vector<int> ret;
int word_size = words[0].size();
int num_word = words.size();
std::unordered_map<string, int> words_table;
for (int i = 0; i < num_word; ++i) {
words_table[words[i]]++;
}
std::unordered_map<string, int> record_table;
for (int i = 0; (i + word_size * num_word) <= s.size(); ++i) {
int j = i;
for (; j < (i + word_size * num_word); j += word_size) {
string sub_str = s.substr(j, word_size);
if (words_table[sub_str] == 0) {
break;
} else {
record_table[sub_str]++;
if (record_table[sub_str] > words_table[sub_str]) {
break;
}
}
}
if (j == (i + word_size * num_word)) {
ret.push_back(i);
}
record_table.clear();
}
return ret;
}
};腾讯云开发者
