ในปัญหานี้ เราเป็นสองสตริง 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'