LeetCode 串联所有单词的子串

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

示例 1：
输入：
s = “barfoothefoobarman”,
words = [“foo”,“bar”]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 “barfoor” 和 “foobar” 。输出的顺序不重要, [9,0] 也是有效答案。

示例 2：

输入：
s = “wordgoodgoodgoodbestword”,
words = [“word”,“good”,“best”,“word”]
输出：[]

提示：如果输入的words不等长则返空处理。

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
	//请在此处填写代码
	}
};

思路分析：比较容易想到的算法思路是对words进行排列组合处理，然后一个一个进行与s串的匹配，寻找下标。但是当words数目比较大时，组合数就是非常之大，并且还要去匹配s串的子串，此种算法的时间复杂度、空间复杂度都非长大。既然倒着不行那可不可顺着从s下手去匹配words呢？（请思考几分钟再往下看！）
下面将以示例一进行分析算法思路。
1、首先利用所有的word总长，在s串中进行截取一段总长长度的子串。
for (int baseIndex = 0; baseIndex <= strInfoLength - allWordLength; ++baseIndex)

每次在s串中从下标baseIndex开始截取allWordLength长度的子串。
2、然而对个第一个取得的子串进行拆分为n个word，去匹配words容器中的word。

3、进行匹配word
完整代码如下

vector<int> findSubstring(string s, vector<string>& words) {
	vector<int> result;//用于存储结果
	const int strInfoLength = s.size();//s串的长度
	const int wordsVecLength = words.size();//words容器长度
	if (wordsVecLength == 0){
		return result;
	}
	const int wordLength = words[0].size();//words中第一个word的长度
	const int allWordLength = wordsVecLength * wordLength;//以第一个word为标准的word总长
	if (strInfoLength < allWordLength){
		//因为所有的word都需要使用上，所以s串的长度必须大于等于所有word的长度和
		return result;
	}
	//对words容器中的各个word长度进行检查，如果发现不等长的，直接返空
	for (int i = 1; i < wordsVecLength; ++i){
		if (words[i].size() != wordLength){
			return result;
		}
	}
	map<string, int> wordTimes;//利用map对所有的word进行标记、
	for (int i = 0; i < wordsVecLength; ++i){
		++wordTimes[words[i]];
	}
	//对s串进行扫描
	for (int baseIndex = 0; baseIndex <= strInfoLength - allWordLength; ++baseIndex){
		//从baseIndex开始每次截取一段allWordLength长度的字符段
		map<string, int> tempWordTimes = wordTimes;//对map容器进行复制
		for (int offsetIndex = 0; offsetIndex < allWordLength; offsetIndex += wordLength){
			//从baseIndex开始的allWordLength长度的字符段中每次截取wordLength个长度，并且进行匹配
			string tempStr(s, baseIndex + offsetIndex, wordLength);
			if (tempWordTimes.count(tempStr) == 0 || tempWordTimes[tempStr] < 1){
				//如果在tempWordTimes不包含tempStr，或者tempStr的次数小于1，则此次匹配终止
				break;
			}
			if (tempWordTimes[tempStr] == 1){
				//如果这个word可使用次数只剩一次，删除这个键值对
				tempWordTimes.erase(tempStr);
			}
			else {
				--tempWordTimes[tempStr];
			}
		}
		if (tempWordTimes.empty()){
			//如果tempWordTimes中所有的word都使用完，则说明此次匹配成功
			result.push_back(baseIndex);
		}
	}
	return result;
}

算法中涉及到部分STL中的vector、map容器，如果不清楚这些知识请自行百度。
但是有点慢

经检查发现代码逻辑出现重复判断

修改后的代码

vector<int> findSubstring(string s, vector<string>& words) {
	vector<int> result;//用于存储结果
	const int strInfoLength = s.size();//s串的长度
	const int wordsVecLength = words.size();//words容器长度
	if (wordsVecLength == 0){
		return result;
	}
	const int wordLength = words[0].size();//words中第一个word的长度
	const int allWordLength = wordsVecLength * wordLength;//以第一个word为标准的word总长
	if (strInfoLength < allWordLength){
		//因为所有的word都需要使用上，所以s串的长度必须大于等于所有word的长度和
		return result;
	}
	//对words容器中的各个word长度进行检查，如果发现不等长的，直接返空
	for (int i = 1; i < wordsVecLength; ++i){
		if (words[i].size() != wordLength){
			return result;
		}
	}
	map<string, int> wordTimes;//利用map对所有的word进行标记
	for (int i = 0; i < wordsVecLength; ++i){
		++wordTimes[words[i]];
	}
	//对s串进行扫描
	for (int baseIndex = 0; baseIndex <= strInfoLength - allWordLength; ++baseIndex){
		//从baseIndex开始每次截取一段allWordLength长度的字符段
		map<string, int> tempWordTimes = wordTimes;//对map容器进行复制
		for (int offsetIndex = 0; offsetIndex < allWordLength; offsetIndex += wordLength){
			//从baseIndex开始的allWordLength长度的字符段中每次截取wordLength个长度，并且进行匹配
			string tempStr(s, baseIndex + offsetIndex, wordLength);
			if (tempWordTimes.count(tempStr) == 0){
				//如果在tempWordTimes不包含tempStr
				break;
			}
			else if (tempWordTimes[tempStr] == 1){
				//如果这个word可使用次数只剩一次，删除这个键值对
				tempWordTimes.erase(tempStr);
			}
			else {
				--tempWordTimes[tempStr];
			}
		}
		if (tempWordTimes.empty()){
			//如果tempWordTimes中所有的word都使用完，则说明此次匹配成功
			result.push_back(baseIndex);
		}
	}
	return result;
}