Leetcode30. Substring with Concatenation of All Words_substring with concatenation of all words idea

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.

Example 1:

Input:
  s = "barfoothefoobarman",
  words = ["foo","bar"]
Output:

[0,9]

Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

Input:
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
Output:

[]

题目大意：

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

做法稍微复杂了一点，总得来说每次有三层比较，只有三层比较都满足，才算成功。

1. 第一次比较是比较每一个单词的首字母的个数和所截字符串分成的单词的首字母是否一致，包括种类与个数。
2. 第二次比较的是所截字符串组里面的所有字母和单词组里面的元素种类个数是否一致。
3. 第三次也是最后的比较是利用哈希表来存储单词组，再用字符串来匹配，这个比较耗时较多，所以不能直接用，否则会超时，所以将它作为最后的防线。

完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include<unordered_map>
using namespace std;
 
bool panduan1(string s,vector<string> &words,int str_len)
{
    vector<int> num1(26, 0);
    for (int i = 0; i < s.length();i+=str_len)
    {
        num1[s[i]-'a']++;
    }
    for (int i = 0; i < words.size();i++)
    {
        num1[words[i][0] - 'a']--;
        if(num1[words[i][0] - 'a']<0)
            return false;
    }
    return true;
}
 
bool panduan2(string s,vector<string> &words,int n)
{
    vector<int> num1(26,0), num2(26,0);
    int g1 = words.size();
    string s2 = "";
    for (int t = 0; t < g1;t++)
    {
        s2 += words[t];
    }
    for (int i = 0; i < n; i++)
    {
        num1[s[i] - 'a']++;
        num2[s2[i] - 'a']++;
    }
    for (int i = 0; i < 26;i++)
    {
        if(num1[i]!=num2[i])
            return false;
    }
    return true;
}
 
bool panduan3(string s,vector<string> &words,int str_len)
{
    unordered_map<string, int> map;
    for (int i = 0; i < words.size();i++)
    {
        if(map.find(words[i]) == map.end())
            map.insert({words[i], 1});
        else
            map[words[i]]++;
    }
    for (int i = 0; i < s.length();i+=str_len)
    {
        string s1 = s.substr(i, str_len);
        if(map.find(s1) == map.end())
            return false;
        else
        {
            map[s1]--;
            if(map[s1]<0)
                return false;
        }
    }
    return true;
}
 
vector<int> findSubstring(string s, vector<string> &words){
    vector<int> shuchu;
    int len = s.length();
    if(len == 0)
        return shuchu;
    int n = words.size();
    if(n == 0)
        return shuchu;
    int str_len = words[0].length();
    int str_len_sum = n * str_len;
    
    for (int q = 0; q <= len-str_len_sum;q++)
    {
        string s1 = s.substr(q, str_len_sum);
        bool t1 = panduan1(s1, words, str_len);
        if(t1 == true)
        {
            bool t2 = panduan2(s1, words, str_len_sum);
            if(t2 == false)
                t1 = false;
            else{
                bool t3 = panduan3(s1, words, str_len);
                    if(t3 == false)
                        t1 = false;
            }
        }
        if(t1 == false)
            continue;
        else
            shuchu.push_back(q);
    }
    return shuchu;
}
 
int main()
{
    string s = "abaababbaba";
    vector<string> words = {"ab","ba","ab","ba"};
    vector<int> num = findSubstring(s, words);
    return 0;
}

占用内存较多。可能是申明了很多数组导致的。。。。