C++で2つの文字列がアナグラムかどうかを判定する方法

2つの文字列「a」と「b」が与えられたと仮定しましょう。この課題では、与えられた2つの文字列が互いにアナグラム（アナグラム：同じ文字を並べ替えてできる別の単語）であるかどうかを判定する必要があります。一方の文字列が、もう一方の文字列とまったく同じ文字（同じ種類・同じ個数）を含んでいるとき、その2つの文字列は互いにアナグラムであると言えます。

具体例

例1

入力：

a = anagram
b = gnarama

出力：

True

解説： 文字列「gnarama」は、文字列「anagram」とまったく同じ文字を同じ個数だけ含んでいます。したがって、True を返します。

例2

入力：

a = programmer
b = mprogretmrqp

出力：

False

解説： 文字列「b」は文字列「a」よりも多くの文字を含んでおり、両者の長さが異なります。このため、False を返します。

解法のアプローチ

この問題を解くために使用するアプローチは以下の通りです。

• まず2つの文字列「a」と「b」を受け取ります。
• ブール型関数 checkAnagram(string a, string b) は、2つの文字列「a」と「b」を受け取り、それらが互いにアナグラムであるかどうかを返します。
• 文字列「a」と「b」の長さを求め、等しいかどうかを確認します。等しくない場合は false を返します。
• C++ の STL（Standard Template Library）の map 関数を使用して、文字列「a」を走査しながら各文字の出現回数をハッシュテーブルに記録します。
• 文字列「a」のマップを作成すると同時に、文字列「b」に含まれる文字をマップから減算していきます。
• 最後にマップ全体を走査し、ハッシュテーブルに残っている文字（カウントが0でない文字）があれば False を返し、なければ True を返します。

実装例（C++コード）

#include<bits/stdc++.h>
using namespace std;
bool checkAnagram(string a, string b){
    int len1= a.length();
    int len2= b.length();
    if(len1!= len2) {
        return false;
    }
    unordered_map <char,int> mp;
    for(int i=0;i<a.size();i++) {
        mp[a[i]]++;
        mp[b[i]]--;
    }
    for(auto it:mp){
        if(it.second) return false;
    }
    return true;
}
int main(){
    string a= "anagram";
    string b= "gnarama";
    cout<< checkAnagram(a,b)<<endl;
    return 0;
}

実行結果

上記のコードを実行すると、次のような出力が得られます。

1

入力された2つの文字列は互いにアナグラムであるため、関数は True、つまり「1」を返します。

このアルゴリズムの計算量は、時間計算量 O(n)、空間計算量 O(n) です。文字の並べ替えを行わずにハッシュマップを使うことで、効率的にアナグラムの判定が可能になります。