สมมติว่าเรามีสองสตริง s1 และ s2 เราต้องเขียนฟังก์ชันให้คืนค่า จริง หาก s2 มีการเรียงสับเปลี่ยนของ s1 เราสามารถพูดได้ว่าการเรียงสับเปลี่ยนของสตริงแรกเป็นสตริงย่อยของสตริงที่สอง ดังนั้นหากสตริง s1 ="abc" และสตริงที่สอง s2 คือ "findcab" ผลลัพธ์จะเป็นจริง เนื่องจากการเปลี่ยนลำดับของ "abc" เป็นจริง นั่นคือ “แท็กซี่”
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- สร้างเวกเตอร์สองตัว cnt1 และ cnt2 ขนาด 26
- สำหรับฉันอยู่ในช่วง 0 ถึง s1
- เพิ่มมูลค่าของ cnt1[s1[i] – 'a'] ขึ้น 1
- j :=0 และต้องการ :=ขนาดของ s1
- สำหรับ i ในช่วง 0 ถึงขนาด s2
- 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'] ทำ
- ลด cnt2[s2[j] – 'a'] ลง 1
- เพิ่ม j ขึ้น 1
- ถ้า i – j + 1 =ขนาดของ s1 และจำเป็น =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
