438. Find all letter words in the string

Meaning:

Given two strings S and p, find the substrings of all ectopic words of p in s, and return the starting indexes of these substrings. The order in which answers are output is not considered.

Ectopic words refer to strings with the same letters but arranged differently.

Example 1:

input: s = "cbaebabacd", p = "abc"
output: [0,6]
explain:
The substring with the starting index equal to 0 is "cba", It is "abc" Ectopic words.
The substring with a starting index equal to 6 is "bac", It is "abc" Ectopic words.

Example 2:

input: s = "abab", p = "ab"
output: [0,1,2]
explain:
The substring with the starting index equal to 0 is "ab", It is "ab" Ectopic words.
The substring with the starting index equal to 1 is "ba", It is "ab" Ectopic words.
The substring with the starting index equal to 2 is "ab", It is "ab" Ectopic words.

The first solution:

I have done two solutions: the first one is done in STL. It needs a number to mark whether the current string meets the needs of the topic. The general idea is:

• First get the number of p strings count
• If the current subscript character is in the p string Enter the cycle, and the number of cycles is the size of p
• The number of flag marks p (not count because the loop body needs to refresh the flag every time), and the flag –
• Judge the number of flag s when the loop is completed If 0 indicates that the current subscript meets the requirements, it will be added to the result container
• If the current subscript matches, you do not need to judge whether each character is the same I just need to judge whether the next character is consistent with the character I deleted (key idea)

This is the first method I thought of, but the time complexity is too high. After running 60 / 60 cases, it times out (I don't understand why). I improved the method later

First solution (timeout):

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
    if(s.size() < p.size() || s.empty())
        return {};
	map<char, int> hash;
	int count = p.size();
	for (const char c : p)
	{
		++hash[c];
	}	
	vector<int> res;
	for (int i = 0; i < s.size() - count + 1; i++)
	{
		if (hash[s[i]] != 0)
		{
			map<char, int> t = hash;
			int flag = count;
			for (int j = 0; j < p.size(); j++)
			{
				if (t[s[i + j]] != 0)
				{
					--t[s[i + j]];
					flag--;
					continue;
				}
				break;
			}
			if (flag == 0)
			{
				res.push_back(i);
				int index = 1;
				while (i + count - 1 + index < s.size() && s[i] == s[i + count - 1 + index])
				{
					res.push_back(i + index);
					i = i + index;
				}
			}
			
		}
	}        
    return res;
    }
};

Operation results:

The second way to solve the problem:

The second is to improve on the idea of the first

• The first point is to replace the map container with an array, which makes the static array time faster
• The second point is to follow the idea of dynamic window. If the added characters are the required characters, I will let count –. If count==0, it means that the current subscript meets the requirements
• Remove the left character. If the left character is the required character, let count + +, so that you can always use count to judge whether the current subscript meets the requirements
• In this way, you only need to traverse the string once, and the time complexity is greatly reduced

The second solution:

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
	if (s.size() < p.size() || s.empty())
		return {};
	int hash[26] = { 0 };
	int map[26] = { 0 };
	int count = p.size();
	for (const char c : p)
	{
		++hash[c - 97];
	}	
	vector<int> res;
	int right = 0;
	int left = 0;
	while (right < s.size())
	{
		while (right - left <= p.size() - 1)
		{
			++map[s[right] - 97];
			if (map[s[right] - 97] <= hash[s[right] - 97])
				count--;
			right++;
		}
		if (count == 0)
		{
			res.push_back(left);
		}
		--map[s[left] - 97];
		if (map[s[left] - 97] < hash[s[left] - 97])
			count++;
		left++;
	}
    return res;
    }
};

Operation results:

Summary:

I've been thinking about this question for a long time. In fact, it is an improved version in the first case. The first time, I didn't judge whether the next character is equal to the character to go out on the left. In this way, the time complexity is greater. All cases ended without passing 60 cases After changing the first situation for a long time, it is found that it is a little outrageous to pass 60 cases and timeout Explain that the idea is not good. I have to start all over again until the next morning. I thought it might be easier if it was similar to sliding window. I tried to do it. The first time I used map. I didn't think it was necessary. Later, I changed it to array, and the time was much faster I was very excited after I finished it (after all, I changed it for a long time) Very satisfied with the timing