Kiểm tra khả năng tạo từ từ tập ký tự cho trước trong C++

Trong bài toán này, cho hai chuỗi str1 và str2. Nhiệm vụ kiểm tra xem tất cả ký tự của str2 có nằm trong str1 hay không.

Ví dụ minh họa:

Đầu vào -

str1 = "Hello" 
str2 = "Hell"

Kết quả - yes

Giải thích - Tất cả ký tự của str2 đều có trong str1.

Để giải bài toán, cách đơn giản là kiểm tra từng ký tự str2 trong str1. Nhưng cần giải pháp hiệu quả. Dùng mảng tần suất (kích thước 256 cho tất cả ký tự hợp lệ). Duyệt str1 tăng tần suất ký tự tương ứng. Duyệt str2 giảm tần suất, và kiểm tra nếu tần suất trở thành âm. Nếu âm thì không thể, ngược lại có thể.

Chương trình minh họa

#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 << "Tất cả ký tự của '" << str2 << "' "; 
    isPresent(str1, str2) ? cout << "có mặt" : cout << "không có mặt"; 
    cout << " trong '" << str1 << "'"; 
    return 0; 
}

Kết quả

Tất cả ký tự của 'point' có mặt trong 'tutorialspoint'