C++で文字列から最も長い偶数長の単語を検索する方法

問題の概要

この問題では、スペースで区切られた複数の単語を含む文字列 str が与えられます。私たちのタスクは、文字列の中から最初に見つかる、最も長い偶数長の単語を検索することです。

言い換えると、長さが最大で、かつ文字数が偶数になっている単語(スペースとスペースの間にある文字列)を抜き出す必要があります。

具体例で問題を確認してみましょう。

Input : str = "learn programming at TutorialsPoint"
Output : TutorialsPoint

説明 −

偶数の長さを持つ単語は「TutorialsPoint」です。

解決アプローチ

この問題に対するシンプルな解決策は、文字列を先頭から走査しながら、「これまでに記録した最長単語よりも長い偶数長の単語」を順次探していくというものです。あらかじめ最長単語の長さ(maxWordLen)を 0 で初期化しておきます。

アルゴリズム

ステップ 1 − 文字列を先頭から順に走査します。

ステップ 2 − 現在の単語の長さが偶数であり、かつ直前に記録した最長単語より長いかどうかをチェックします。

ステップ 3 − 条件を満たす中で最も長い単語を返します。

C++での実装例

以下は、このソリューションの動作を示すサンプルプログラムです。

#include <bits/stdc++.h>
using namespace std;
string findMaxEvenLenWord(string str) {
    int len = str.length();
    int i = 0; int currWordlen = 0;
    int maxWordLen = 0;
    int stringPointer = -1;
    while (i < len) {
        if (str[i] == ' ') {
            if (currWordlen % 2 == 0) {
                if (maxWordLen < currWordlen) {
                    maxWordLen = currWordlen;
                    stringPointer = i - currWordlen;
                }
            }
            currWordlen = 0;
        }
        else {
            currWordlen++;
        }
        i++;
    }
    if (currWordlen % 2 == 0) {
        if (maxWordLen < currWordlen) {
            maxWordLen = currWordlen;
            stringPointer = i - currWordlen;
        }
    }
    if (stringPointer == -1)
        return "Not Found!";
    return str.substr(stringPointer, maxWordLen);
}
int main() {
   string str = "Learn programming at Tutorialspoint";
   cout<<"The maximum length even word is '"<<findMaxEvenLenWord(str)<<"'";
   return 0;
}

実行結果

The maximum length even word is 'Tutorialspoint'

計算量

このアルゴリズムは文字列全体を一度だけ走査するため、時間計算量は O(n) となります(n は文字列の長さ)。また、追加のメモリとしては定数個の変数しか使用しないため、補助空間計算量は O(1) です。