アナグラム - tanakakenji/Rinko GitHub Wiki

C++でのアナグラム判定テクニック

アナグラムとは、ある単語や句の文字を並べ替えて別の単語や句を作ることです。ここでは、2つの文字列がアナグラムであるかどうかを判定する3つの異なるアプローチを、C++のコード例を用いて解説します。

1. ソートを使用する方法

この方法では、両方の文字列をソートし、結果が同じであればアナグラムと判定します。

実装

#include <iostream>
#include <string>
#include <algorithm>

bool areAnagramsSort(std::string s1, std::string s2) {
    if (s1.length() != s2.length()) return false;
    
    std::sort(s1.begin(), s1.end());
    std::sort(s2.begin(), s2.end());
    
    return s1 == s2;
}

int main() {
    std::string str1 = "listen";
    std::string str2 = "silent";
    std::cout << str1 << " and " << str2 << " are anagrams: " 
              << (areAnagramsSort(str1, str2) ? "Yes" : "No") << std::endl;
    
    return 0;
}

解説

  • 時間複雑度: O(n log n) - ソートにかかる時間
  • 空間複雑度: O(log n) - 多くのソートアルゴリズムが使用する追加の空間

この方法は簡単に実装できますが、ソートの時間複雑度が高いため、大きな文字列や多数の文字列を処理する場合には効率が悪くなる可能性があります。

2. 素数マッピングを使用する方法

各文字を素数にマッピングし、それらを掛け合わせた結果が同じであればアナグラムと判定します。

実装

#include <iostream>
#include <string>
#include <array>

bool areAnagramsPrime(const std::string& s1, const std::string& s2) {
    if (s1.length() != s2.length()) return false;
    
    const std::array<int, 26> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 
                                        43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
    
    long long product1 = 1, product2 = 1;
    
    for (char c : s1) product1 *= primes[c - 'a'];
    for (char c : s2) product2 *= primes[c - 'a'];
    
    return product1 == product2;
}

int main() {
    std::string str1 = "eat";
    std::string str2 = "tea";
    std::cout << str1 << " and " << str2 << " are anagrams: " 
              << (areAnagramsPrime(str1, str2) ? "Yes" : "No") << std::endl;
    
    return 0;
}

解説

  • 時間複雑度: O(n) - 各文字列を一度だけ走査
  • 空間複雑度: O(1) - 固定サイズの配列と2つの変数のみ使用

この方法は高速ですが、非常に長い文字列の場合、整数オーバーフローの可能性があることに注意が必要です。

3. 文字の頻度カウントを使用する方法

各文字の出現回数をカウントし、両方の文字列で同じ頻度であればアナグラムと判定します。

実装

#include <iostream>
#include <string>
#include <array>

bool areAnagramsCount(const std::string& s1, const std::string& s2) {
    if (s1.length() != s2.length()) return false;
    
    std::array<int, 26> count = {0};
    
    for (char c : s1) count[c - 'a']++;
    for (char c : s2) count[c - 'a']--;
    
    for (int i : count) {
        if (i != 0) return false;
    }
    
    return true;
}

int main() {
    std::string str1 = "anagram";
    std::string str2 = "nagaram";
    std::cout << str1 << " and " << str2 << " are anagrams: " 
              << (areAnagramsCount(str1, str2) ? "Yes" : "No") << std::endl;
    
    return 0;
}

解説

  • 時間複雑度: O(n) - 各文字列を一度だけ走査し、最後にカウント配列を確認
  • 空間複雑度: O(1) - 固定サイズの配列のみ使用

この方法は効率的で、オーバーフローの心配もなく、多くの場合で最適な選択肢となります。

まとめ

  1. ソート法:

    • 簡単に実装できるが、時間複雑度が高い
    • 大きな文字列や多数の文字列を処理する場合には適していない

  2. 素数マッピング法:

    • 非常に高速だが、長い文字列でオーバーフローの可能性がある
    • ユニークな素数の選択が重要

  3. 頻度カウント法:

    • 効率的で安全、多くの場合で最適
    • 実装も比較的簡単

実際の使用では、問題の制約（文字列の長さ、文字セットなど）と要求されるパフォーマンスに基づいて、適切な方法を選択することが重要です。一般的には、頻度カウント法が最もバランスの取れた選択肢となることが多いでしょう。

⚠️ **GitHub.com Fallback** ⚠️