【C++】文字列内の最短語と最長語を検索するプログラムの作成方法

問題概要

本記事では、与えられた文字列 str の中から最も短い単語(最短語)と最も長い単語(最長語)を検索するプログラムをC++で作成する方法を解説します。

問題の説明 ― 文字列が1つ与えられます。その文字列に含まれるすべての単語の中から、文字数が最も多い単語と最も少ない単語を求めます。なお、単語は半角スペースまたはNULL文字('\0')で区切られているものとします。

入力例

str = “Learn Programming at TutorialsPoint”

出力例

smallest word = at
largest word = Tutorialspoint

解決アプローチ

最短語と最長語を見つけるには、まず各単語の長さを求める必要があります。そこで、単語の開始位置を示すインデックス(startIndex)と、終了位置を示すインデックス(endIndex)の2つを使用します。単語の終わりは、スペース(' ')またはNULL文字('\0')によって判定できます。

startIndex と endIndex が確定すれば、現在の単語の長さ(currentLength)を計算できます。この長さをこれまで記録しておいた minLength / maxLength と比較し、条件を満たしていれば smallest / largest を更新していきます。

アルゴリズムの手順

1. endIndex を先頭から順に進め、スペースまたはNULL文字に到達したら単語の区切りとみなす。
2. currentLength = endIndex − startIndex として、現在の単語の長さを求める。
3. currentLength が minLength より小さい場合、smallest と minLength を更新する。
4. currentLength が maxLength より大きい場合、largest と maxLength を更新する。
5. startIndex を endIndex の次の位置に移動し、文字列の末尾に達するまで手順1〜4を繰り返す。

C++実装例

#include<iostream>
#include<cstring>
using namespace std;

void minMaxLengthWords(string str){
    int StrLength = str.length();
    int startIndex = 0, endIndex = 0;
    int minLength = StrLength, maxLength = 0, currentLength;
    string smallest, largest;
    while (endIndex <= StrLength){
        if (str[endIndex] != '\0' && str[endIndex] != ' ')
            endIndex++;
        else{
            currentLength = endIndex - startIndex;
            if (currentLength < minLength){
                smallest = str.substr(startIndex, currentLength);
                minLength = currentLength;
            }
            if (currentLength > maxLength){
                largest = str.substr(startIndex, currentLength);
                maxLength = currentLength;
            }
            endIndex++;
            startIndex = endIndex;
        }
    }
    cout<<"Smallest Word from the string is "<<smallest<<"\n";
    cout<<"Largest Word from the string is "<<largest;
}

int main() {
    string a = "Learn Programming at TutorialsPoint";
    minMaxLengthWords(a);
}

実行結果

Smallest Word from the string is at
Largest Word from the string is TutorialsPoint

まとめ

このアルゴリズムは、文字列を先頭から一度だけ走査すれば最短語と最長語の両方を求められるため、時間計算量は O(n) という非常に効率的な手法です。2つのインデックスを用いて単語の境界を検出する考え方は、文字列分割やトークン化など、さまざまな文字列処理の基礎となるテクニックです。ぜひ理解を深めておきましょう。