LeetCode 30. Substring with Concatenation of All Words（词语拼接组合）

题目描述：

    You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
    For example, given:

    s: "barfoothefoobarman"
    words: ["foo", "bar"]

    You should return the indices: [0,9].
    (order does not matter).

分析：
    题意：给定一个字符串S、一个单词字符串组成的数组words。查找所有满足条件的坐标：S中以该坐标开始的某个连续子串，包含了words中所有单词恰好一次。返回所有满足的坐标集合。
    思路：假设S长度为n1，words长度为n2，words每个单词长度为n3。我们用一个map统计words中出现的所有单词，并且从S中任意i位置开始，考察连续n2个n3长度的子字符串：如果某个子字符串在map中没有出现，则i位置不符合；如果出现了，则map中减去相应单词的出现次数。一轮结束，如果map清空，则找到了一个符合条件的i位置，加入答案中。重复该步骤，直到获取所有满足的坐标。
    时间复杂度为O((n1 - n2 * n3) * n2)。

代码：

#include <bits/stdc++.h>
 
using namespace std;
 
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
		int n2 = words.size();
		// Exceptional Case 1: 
		if(n2 == 0){
			return vector<int>();
		}
		vector<int> ans;
        int n1 = s.length(), n3 = words[0].length();
		// debug
		// cout << "n1: " << n1 << ", n2: " << n2 << ", n3: " << n3 << endl;
		// Exceptional Case 2: 
		if(n3 == 0){
			for(int i = 0; i <= n1; i++){
				ans.push_back(i);
			}
			return ans;
		}
		map<string, int> m1, m2;
		// save the words information
		for(int i = 0; i <= n2 - 1; i++){
			m1[words[i]]++;
		}
		for(int i = 0; i <= n1 - n2 * n3; i++){
			m2 = m1;
			for(int j = 0; j <= n2 - 1; j++){
				string str = s.substr(i + j * n3, n3);
				if(m2.count(str)){
					m2[str]--;
					if(m2[str] == 0){
						m2.erase(str);
					}
				}
				else{
					break;
				}
			}
			if(m2.size() == 0){
				ans.push_back(i);
			}
		}
		return ans;
    }
};