C++で文字列内のセグメント数を数える方法

問題概要

文字列 s が与えられたとき、その文字列に含まれる「セグメント」の数を数えます。ここでセグメントとは、空白文字を含まない連続した文字の並びのことを指します。

たとえば、入力が "Hello, I love programming" の場合、セグメントは4つ存在するため、出力は4になります。

解法のアプローチ

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

• カウンタ n を 0 で初期化します。
• i を 0 から文字列の長さ未満まで1ずつ増やしながらループ処理を行います。
  • s[i] が空白でない場合、n を1増やします（新しいセグメントの開始を検出）。
  • その後、i が文字列の範囲内であり、かつ s[i] が空白でない間、i を進めます（現在のセグメントの残りを読み飛ばす）。
• 最後に n を返します。

アルゴリズムのポイント

このアルゴリズムでは、空白以外の文字が出現した時点で「新しいセグメントの始まり」と判断し、カウントを1つ増やします。その直後に、そのセグメントの残りの部分を一気に読み飛ばすことで、同じセグメントを二重にカウントしてしまうことを防いでいます。

文字列を一度だけ走査すればよいため、時間計算量は O(n)、必要な追加メモリは O(1) と非常に効率的です。

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int countSegments(string s) {
        int n = 0;
        for(int i = 0; i < s.size(); i++){
            if(s[i] != ' ')
                n++;
            while( i < s.size() && s[i] != ' ')
                i++;
        }
        return n;
    }
};
main(){
    Solution ob;
    cout << (ob.countSegments("Hello, I love programming"));
}

入力

"Hello, I love programming"

出力

4