두 개의 문자열 s1과 s2가 있다고 가정하고 s2에 s1의 순열이 포함되어 있으면 true를 반환하는 함수를 작성해야 합니다. 따라서 첫 번째 문자열의 순열 중 하나가 두 번째 문자열의 하위 문자열이라고 말할 수 있습니다. 따라서 문자열 s1 ="abc"이고 두 번째 문자열 s2가 "findcab"이면 결과는 "abc"의 순열이 참이므로 참이 됩니다. 바로 "택시"입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 크기가 26인 두 벡터 cnt1 및 cnt2 생성
- 0에서 s1 사이의 i에 대해
- cnt1[s1[i] – 'a']의 값을 1 증가
- j :=0 및 필수 :=s1의 크기
- 0에서 s2 크기까지의 i에 대해
- x :=s2[i]
- cnt2[x – 'a'] 1씩 증가
- cnt1[x – 'a'] 및 cnt2[x – 'a'] <=cnt[x – 'a']이면
- 1 감소 필요
- j <=i이고 cnt2[s2[j] – 'a'] – 1>=cnt1[s2[j] – 'a'], do
- cnt2[s2[j] – 'a'] 1 감소
- j를 1 증가
- i – j + 1 =s1의 크기이고 required =0이면 true를 반환합니다.
- 거짓을 반환합니다.
예(C++)
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool checkInclusion(string s1, string s2) {
vector <int> cnt1(26), cnt2(26);
for(int i = 0; i < s1.size(); i++)cnt1[s1[i] - 'a']++;
int j = 0;
int required = s1.size();
for(int i = 0; i < s2.size(); i++){
char x = s2[i];
cnt2[x - 'a']++;
if(cnt1[x - 'a'] && cnt2[x - 'a'] <= cnt1[x - 'a']) required--;
while(j <= i && cnt2[s2[j] - 'a'] - 1 >= cnt1[s2[j] - 'a']){
cnt2[s2[j] - 'a']--;
j++;
}
if(i - j + 1 == s1.size() && required == 0){
return true;
}
}
return false;
}
};
main(){
Solution ob;
cout << (ob.checkInclusion("abc", "findcab"));
} 입력
"abc" "findcab"
출력
1