พิมพ์คู่ Anagrams ในอาร์เรย์สตริงใน C++

ภาพรวมปัญหา

ได้รับอาร์เรย์สตริง ต้องพิมพ์คู่ Anagrams ทั้งหมด (สตริงที่จัดเรียงตัวอักษรแล้วเหมือนกัน)

ตัวอย่าง

Input: {"hello", "hrdef", "from", "lohel", "morf"}
Output: [hello, lohel], [from, morf]

วิธีแก้ปัญหา (Nested Loops + Character Count)

1. ลูปซ้อน 2 ชั้น เลือกคู่สตริง
2. นับความถี่ตัวอักษร 256 ตัว ถ้าเท่ากันทุกตัว → Anagram

ตัวอย่างโค้ด C++

#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] << " and " << arr[j] << " are anagrams.\n";
}

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

ผลลัพธ์ (Output)

hello and lohel are anagrams.
from and morf are anagrams.

การเพิ่มประสิทธิภาพ

เรียงอาร์เรย์สตริงก่อน (Sort each string) แล้ว Anagram จะติดกัน → ลด Complexity