C++で2つの文字列に共通しない文字を検索する方法

このチュートリアルでは、C++を使って、与えられた2つの文字列の中から「片方にしか存在しない文字」を効率的に見つける方法を解説します。まずは具体例を見てみましょう。

入力例と出力例

入力

string_one = "tutorialspoint"
string_two = "tutorialsworld"

出力

d n p w

上記の例では、両方の文字列に共通して含まれる文字(t、u、o、r、i、a、l、s)を除き、どちらか一方にのみ存在する文字 d、n、p、w を出力しています。

解法のアプローチ

この問題はハッシュ(連想配列)を使うことで効率的に解けます。2重ループで全文字同士を比較する方法よりも計算量が少なく、パフォーマンス面で優れています。

解決手順

• 2つの文字列を適当な値で初期化します。
• map<char, int> 型のマップ chars を用意します。
• 1つ目の文字列を走査し、各文字をキーとして値1でマップに挿入します。
• 次に2つ目の文字列を走査します。
  • その文字がすでにマップに存在するかどうかを確認します。
  • 存在する場合は、共通文字であることを示すため値を0に更新します。
  • 存在しない場合は、新しい文字として値1で挿入します。
• 最後にマップ全体を走査し、値が1の文字(=片方にしか存在しない文字)を出力します。

サンプルコード

以下が実際のコードです。

#include <bits/stdc++.h>
#include <map>
using namespace std;

void findDistinctCharacters(string one, string two){
    // 文字の出現状況を記録するマップを初期化
    map<char, int> chars;
    // 1つ目の文字列を走査
    for (int i = 0; i < one.size(); ++i){
        // 各文字をマップに挿入
        chars.insert({one[i], 1});
    }
    // 2つ目の文字列を走査
    for (int i = 0; i < two.size(); ++i){
        // 現在の文字がすでに登録されているか確認
        if (chars.count(two[i])) {
            // 共通文字には0を設定
            chars.find(two[i])->second = 0;
        }
        else {
            // 新しい文字を挿入
            chars.insert({two[i], 1});
        }
    }
    // 共通しない文字を出力
    for (auto item : chars){
        // 値が1の文字だけ出力
        if (item.second == 1) {
            cout << item.first << " ";
        }
    }
}

int main(){
    string one = "tutorialspoint";
    string two = "tutorialsworld";
    findDistinctCharacters(one, two);
    return 0;
}

実行結果

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

d n p w

まとめ

std::map を活用することで、2つの文字列をそれぞれ一度ずつ走査するだけで共通しない文字を抽出できました。時間計算量は O(N log N)(Nは文字数の合計)となり、単純な2重ループによる O(N²) のアプローチより大幅に高速です。なお、順序を気にせずさらに高速化したい場合は unordered_map を使うことで平均 O(N) に改善できます。チュートリアルについて質問がある場合は、コメント欄でお知らせください。