C++で文字列内の最も長い数値を検索する方法

問題の概要

この問題では、文字と英字のみで構成される文字列 str が与えられます。私たちのタスクは、文字列内で最も桁数の多い数値を見つけることです。

問題の詳細: 文字列内に含まれる連続した数字の並び(数値)の中から、最も桁数が大きいものを特定する必要があります。

具体例で問題を理解しよう

• 入力: str = "code001tutorials34124point"
• 出力: 34124

説明:

この文字列に含まれる数値は以下の通りです。

• 001 → 桁数 3
• 34124 → 桁数 5

このうち最も桁数が多いのは「34124」であるため、これが答えとなります。

解決アプローチ

この問題に対するシンプルな解決策は、文字列を先頭から順に走査し、各数値の桁数と開始インデックスを特定することです。文字列中の各数値について、開始位置と連続する数字の文字数を記録していき、最終的に最も長い数値を返します。

アルゴリズムの流れは以下の通りです。

1. 文字列を1文字ずつ走査します。
2. 現在の文字が数字(isdigit)である限り、カウントを増やしながら前へ進みます。
3. 数字の並びが途切れた時点で、これまでの最大桁数と比較します。
4. より長い数値が見つかった場合は、その開始位置と桁数を更新します。
5. 走査が完了したら、記録しておいた開始位置と長さをもとに部分文字列を返します。

ソリューションの実装例

#include <iostream>
using namespace std;

string findLongestNumber(string str, int l) {

    int count = 0, max = 0, maxLenPos = -1, currPos, currLen, maxLen = 0;

    for (int i = 0; i < l; i++) {
        currPos = maxLenPos;
        currLen = maxLen;
        count = 0;
        maxLen = 0;
        if (isdigit(str[i]))
            maxLenPos = i;
        while (isdigit(str[i])) {
            count++;
            i++;
            maxLen++;
        }
        if (count > max) {
            max = count;
        }
        else {
            maxLenPos = currPos;
            maxLen = currLen;
        }
    }
    return (str.substr(maxLenPos, maxLen));
}

int main() {

    string str = "code001tutorials34124point";
    int l = str.length();
    cout<<"The longest length number in string is "<<findLongestNumber(str, l);
    return 0;
}

実行結果

The longest length number in string is 34124

コードのポイント

• isdigit() 関数を使用して、現在の文字が数字かどうかを判定しています。
• maxLenPos には現時点で最も長い数値の開始位置が、maxLen にはその桁数が保持されます。
• 新しく見つかった数字の並びが既存の最大桁数を超えた場合のみ、開始位置と桁数を更新します。
• 最後に substr() を使って該当する数値を文字列として取り出し、結果として返します。

計算量

時間計算量: O(n) ― 文字列全体を一度だけ走査すればよいためです。
空間計算量: O(1) ― 追加で必要な記憶領域は、位置と長さを管理する少数の変数のみです。