描述

tag

Companies

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.

中文

大概意思是在字符串s中找出由等长的单词全排列形成的子串

思路

首先想到的是找出words的全排列
然后就是判断s中是否存在这些全排列， 后来觉得这样复杂度有点高

后来根据搜索， 有了点思路，可以叫做生长法

生长的起点一共有m个(m是单词的长度)
每次生长一个单词的长度，长对了就继续长，直到总长等于所需的。
长错了

1. 新的单词不在 words 中， 清空，从下一个单词重新生长
2. 长过了，目标中某个单词的数目超了，把数目减去，减到正常

class Solution
{
public:
    vector<int> findSubstring(string s, vector<string>& words)
    {
        vector<int> res;
        int sLength = s.length();
        int wordsSize = words.size();
        if (sLength == 0 || wordsSize == 0) return res;
        int m = words[0].length();
        if (m == 0 || m * wordsSize > sLength) return res;
        unordered_map<string, int> wordsMap;
        for (int i = 0; i < wordsSize; ++i)
        {
            if (wordsMap.find(words[i]) == wordsMap.end())
                wordsMap[words[i]] = 1;
            else
                ++wordsMap[words[i]];
        }
        for (int seed = 0; seed < m; ++seed)
        {
            unordered_map<string, int> growthRes;
            int growthNum = 0;
            for (int i = seed; i <= sLength - m; i += m)
            {
                string tmp = s.substr(i, m);
                if (wordsMap.find(tmp) == wordsMap.end())
                {
                    growthRes.clear();
                    growthNum = 0;
                }
                else
                {
                    if (growthRes.find(tmp) == wordsMap.end())
                        growthRes[tmp] = 1;
                    else
                        ++growthRes[tmp];
                    ++growthNum;
                    while (wordsMap[tmp] < growthRes[tmp])
                    {
                        string tmpRemove = s.substr(i - (growthNum - 1) * m, m);
                        --growthRes[tmpRemove];
                        --growthNum;
                    }
                    if (growthNum == wordsSize) res.push_back(i - (wordsSize - 1) * m);
                }
            }
        }
        return res;
    }
};