C++で文字列がaⁿbⁿパターンに一致するかどうかを判定する方法

この問題では、「a」と「b」の2種類の文字のみで構成された文字列が与えられます。その文字列が aⁿbⁿ の形式、つまり「n個のa」の後に「n個のb」が続く形になっているかどうかを判定します。条件を満たす場合は1を、満たさない場合は0を返します。

例えば、入力が「aaaaaaaaaaaabbbbbbbbbbbb」の場合、aが12個、その後にbが12個続いているため、出力は1（true）となります。

解決のためのアプローチ

この問題は、以下の手順で解決できます。

• まず、入力文字列の長さを取得します。
• 先頭から順に文字を走査し、文字が「a」である限りループを続けます。「a」以外の文字が出現した時点でループを抜けます。このときのインデックスiは「a」の個数を表します。
• i × 2 が文字列全体の長さと等しくない場合、aとbの個数が一致しないため false を返します。
• 位置iから文字列の末尾まで走査し、すべての文字が「b」であることを確認します。途中で「b」以外の文字が見つかった場合は false を返します。
• すべてのチェックを通過できれば true を返します。

C++での実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
bool solve(string input_string) {
    int length = input_string.length();
    int i;
    for (i = 0; i < length; i++)
       if (input_string[i] != 'a')
          break;
    if (i * 2 != length)
       return false;
    for (int j = i; j < length; j++)
       if (input_string[j] != 'b')
          return false;
   return true;
}
int main() {
    string input_string = "aaaaaaaaaaaabbbbbbbbbbbb";
    cout << solve(input_string) << endl;
    return 0;
}

入力

"aaaaaaaaaaaabbbbbbbbbbbb"

出力

1

その他の入力例と判定結果

• 「aabb」→ 1（aが2個、その後にbが2個）
• 「aaab」→ 0（aとbの個数が一致しない）
• 「abab」→ 0（bの後にaが出現している）
• 「aaa」→ 0（bが存在しない）

計算量について

このアルゴリズムは文字列を最大2回走査するだけで済むため、時間計算量はO(n)、追加のメモリを使用しないため空間計算量はO(1)と非常に効率的です。スタックや正規表現を使わずに、シンプルな線形走査でaⁿbⁿパターンの判定が可能です。