ความเป็นไปได้ของคำจากชุดตัวอักษรที่กำหนดใน C++

ในปัญหานี้ เราได้รับสตริงสองสตริง str1 และ str2 งานของเราคือตรวจสอบว่าตัวอักษรทั้งหมดของ str2 อยู่ใน str1 หรือไม่

มาดูตัวอย่างเพื่อเข้าใจปัญหา:

Input -

str1 = "Hello"
str2 = "Hell"

Output - yes

Explanation - ตัวอักษรทั้งหมดของ str2 อยู่ใน str1

เพื่อแก้ปัญหานี้ วิธีแก้ง่ายๆ จะเป็นการตรวจสอบตัวอักษรแต่ละตัวของ str2 ใน str1 แล้วส่งคืนโซลูชัน

แต่เราต้องสร้างโซลูชันที่มีประสิทธิภาพ ดังนั้นเราจะใช้ frequency array (ความยาว 256 สำหรับตัวอักษรที่ถูกต้องทั้งหมด) แล้วท่อง str1 และเพิ่มค่าใน frequency array ตามตัวอักษรที่เกี่ยวข้องที่เกิดขึ้น แล้วเราจะท่อง str2 ซึ่งจะลดค่า frequency array เมื่อเกิดขึ้น และในแต่ละรอบ เราจะตรวจสอบว่าความถี่นี้กลายเป็นลบหรือไม่ หากเป็น แสดงว่าไม่เป็นไปได้ มิฉะนั้นเป็นไปได้

ตัวอย่าง

โปรแกรมแสดงการนำโซลูชันของเราไปใช้งาน:

#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 characters of '" << str2 << "' are ";
    isPresent(str1, str2) ? cout << "present" : cout << "not present";
    cout << " in '" << str1 << "' ";
    return 0;
}

ผลลัพธ์

All characters of 'point' are present in 'tutorialspoint'