【C++】ある文字列のすべての文字が別の文字列に含まれるか判定する方法

問題概要

この問題では、2つの文字列 str1 と str2 が与えられます。求められるのは、str2 を構成するすべての文字が str1 に存在するかどうかを判定することです。

入力例

str1 = "Hello"
str2 = "Hell"

出力例

Yes

説明： str2 のすべての文字(H、e、l、l)は str1 に存在するため、答えは「Yes」となります。

シンプルな解法とその課題

最も単純なアプローチは、str2 の各文字について str1 内を走査し、その文字が存在するかを1つずつ確認する方法です。しかしこの方法では、最悪の場合 O(n×m) の時間計算量が必要となり、文字列が長くなるほど非効率になります。

効率的な解法：頻度配列の活用

より効率的に解くためには、頻度配列(frequency array)を利用します。手順は以下の通りです。

1. 扱うすべての文字に対応できるよう、長さ256の整数型配列を用意して 0 で初期化します。
2. まず str1 を走査し、出現した各文字に対応する要素のカウントを +1 していきます。
3. 次に str2 を走査し、出現した各文字に対応するカウントを −1 します。このときカウントが負になった場合は、必要な文字の数が足りないことを意味するため、即座に「存在しない」と判定して false を返します。
4. 最後まで問題なく走査できれば、str2 のすべての文字が str1 に含まれていると判断でき、true を返します。

この手法では、時間計算量が O(n + m)(n、m はそれぞれの文字列の長さ)、空間計算量は固定サイズの配列1つのみで済むため O(1) となります。

C++での実装例

上記の解法を C++ で実装したプログラムが次のとおりです。

#include <iostream>
#include <string.h>
using namespace std;
bool isPresent(string str1, string str2){
    int freq[256] = { 0 };
    // str1 の各文字の出現回数をカウント
    for (int i = 0; i < str1.length(); i++)
        freq[(unsigned char)str1[i]]++;
    // str2 の各文字に対応するカウントを消費
    for (int i = 0; i < str2.length(); i++) {
        freq[(unsigned char)str2[i]]--;
        if (freq[(unsigned char)str2[i]] < 0)
            return false;
    }
    return true;
}
int main() {
    string str1 = "tutorialspoint";
    string str2 = "point";
    cout << "'" << str2 << "' のすべての文字は '" << str1 << "' の中に";
    isPresent(str1, str2) ? cout << "存在します" : cout << "存在しません";
    return 0;
}

実行結果

'point' のすべての文字は 'tutorialspoint' の中に存在します

まとめ

文字の出現回数を配列で管理する「頻度配列」のテクニックは、アナグラム判定など、さまざまな文字列処理の問題に応用できる基本的かつ強力な手法です。線形時間で処理が完了するため、大きな文字列を扱う場合にも有効です。ぜひ他の問題でも活用してみてください。