In Tất Cả Các Cặp Anagram Trong Mảng Chuỗi Cho Trước Trong C++

Trong bài toán này, chúng ta được cho một mảng chuỗi và phải in tất cả các cặp anagram của mảng đó.

Anagram là chuỗi được tạo bằng cách sắp xếp lại ký tự của chuỗi khác. Ví dụ: hello và lolhe.

Ví dụ để hiểu vấn đề:

Đầu vào: mảng = {"hello", "hrdef", "from", "lohel", "morf"} → Đầu ra: [hello, lohel], [from, morf]

Để giải quyết, ta dùng lồng vòng lặp. Vòng ngoài duyệt mảng chọn phần tử. Vòng trong kiểm tra từng chuỗi và xem có phải anagram không.

Ví Dụ

Chương trình triển khai thuật toán:

#include <iostream>
using namespace std;
#define NO_OF_CHARS 256

bool isAnagramString(string str1, string str2) {
    int count[NO_OF_CHARS] = {0};
    int i;
    for (i = 0; str1[i] && str2[i]; i++) {
        count[str1[i]]++;
        count[str2[i]]--;
    }
    if (str1[i] || str2[i])
        return false;
    for (i = 0; i < NO_OF_CHARS; i++)
        if (count[i])
            return false;
    return true;
}

void printAnagrams(string arr[], int n) {
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (isAnagramString(arr[i], arr[j]))
                cout << arr[i] << " và " << arr[j] << " là anagram.\n";
}

int main() {
    string arr[] = {"hello", "hrdef", "from", "lohel", "morf"};
    int n = sizeof(arr) / sizeof(arr[0]);
    printAnagrams(arr, n);
    return 0;
}

Đầu Ra

hello và lohel là anagram.
from và morf là anagram.

Giải pháp này dễ hiểu nhưng kém hiệu quả. Có thể tối ưu bằng cách sắp xếp mảng chuỗi để tìm anagram dễ dàng hơn.