ในปัญหานี้ เราเป็นสองสตริง str1 และ str2 งานของเราคือตรวจสอบว่าอักขระทั้งหมดของ str2 และแสดงอยู่ใน str1 หรือไม่
มาดูตัวอย่างทำความเข้าใจปัญหากัน
ป้อนข้อมูล −
str1 = “Hello” str2 = “Hell”
ผลผลิต − ใช่
คำอธิบาย - อักขระทั้งหมดของ str2 มีอยู่ใน str1
ในการแก้ปัญหานี้ วิธีแก้ไขง่ายๆ จะตรวจสอบอักขระแต่ละตัวของ str2 ใน str1 แล้วส่งคืนโซลูชัน
แต่เราต้องสร้างโซลูชันที่มีประสิทธิภาพ ดังนั้น เราจะใช้อาร์เรย์ความถี่ (ความยาว 256 สำหรับอักขระที่ถูกต้องทั้งหมด) จากนั้นข้ามผ่าน str1 และเพิ่มค่าในอาร์เรย์ความถี่ตามอักขระที่เกี่ยวข้องมากกว่าที่เกิดขึ้น จากนั้นเราจะสำรวจ str2 ซึ่งจะลดความถี่อาร์เรย์เมื่อเกิดขึ้น และในการทำซ้ำแต่ละครั้ง เราจะตรวจสอบด้วยว่าความถี่นี้เป็นลบหรือไม่ ถ้ามันเป็นไปไม่ได้ อย่างอื่นก็เป็นไปได้
ตัวอย่าง
โปรแกรมแสดงการใช้งานโซลูชันของเรา
#include <iostream>
#include <string.h>
using namespace std;
bool isPresent(string str1, string str2){
int freq[256] = { 0 };
for (int i = 0; i<str1.length(); i++)
freq[str1[i]]++;
for (int i=0;i<str2.length(); i++) {
if (freq[str2[i]] < 1)
return false;
}
return true;
}
int main() {
string str1 = "tutorialspoint";
string str2 = "point";
cout<<"All charcters of '"<<str2<<"' are ";
isPresent(str1,str2)?cout<<"present":cout<<"not present";
cout<<" in '"<<str1<<"' ";
return 0;
} ผลลัพธ์
All charcters of 'point' are present in 'tutorialspoint'
