leetcode 567) Permutation in String

LV. Medium 🧐

https://leetcode.com/problems/permutation-in-string/

Permutation in String - LeetCode

 

문제

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1's permutations is the substring of s2.

 

Example 1:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

 

Constraints:

• 1 <= s1.length, s2.length <= 10^4
• s1 and s2 consist of lowercase English letters.

 

문제 해결법

다 확인하는 부르트포스 방식으로 푸니 타임 엑시드..

슬라이딩 윈도우라는 좋은 알고리즘 발견!

 

s1의 값을 저장해놓는 배열을 둔다.

그리고 s2에서 s1의 크기만큼 보면서 그 조합 안에 s1의 값들이 있나 확인하면 끝!

 

해결 코드

class Solution {
public:
	bool checkInclusion(string s1, string s2) {
		if (s1.length() > s2.length())
			return false;

		vector<int> s1_m(26, 0);
		vector<int> s2_m(26, 0);
		for (int i = 0; i < s1.length(); ++i) {
			s1_m[s1[i] - 'a']++;
			s2_m[s2[i] - 'a']++;
		}
		for (int i = 0; i < s2.length() - s1.length(); ++i) {
			if (match(s1_m, s2_m))
				return true;
			s2_m[s2[i] - 'a']--;
			s2_m[s2[i + s1.length()] - 'a']++;
		}
		return false;
	}
	bool match(vector<int> &s1_m, vector<int> &s2_m) {
		for (int i = 0; i < 26; ++i) {
			if (s1_m[i] != s2_m[i])
				return false;
		}
		return true;
	}
};