C++で英語表記の文字列から元の数字を復元するアルゴリズム

0〜9の数字を表す英単語（zero、one、two、three、four、five、six、seven、eight、nine）が、順番を入れ替えた状態で1つの文字列に連結されて与えられます。この文字列から元の数字を読み取り、昇順に出力するのが本記事のテーマです。この問題には次のような特徴があります。

• 入力は必ず有効であり、必ず元の数字列へと復元できることが保証されています。つまり「abc」や「zerone」のような無効な入力は考慮不要です。
• 入力の長さは50,000未満です。

たとえば、入力が「fviefuro」（five と four の並び替え）であれば、出力は「45」となります。

解法のポイント：数字ごとに「固有の文字」を見つける

この問題を効率的に解く鍵は、一部の数字にしか登場しない文字に着目することです。まず文字の出現回数をすべて数え、その後、ほかの数字との重複分を順に差し引いていくことで、各数字の個数を確定できます。

ステップ1：一意な文字だけで確定できる数字

次の4文字は、それぞれ1つの数字にしか現れないため、出現回数を数えるだけで個数がすぐにわかります。

• 'z' → zero（0）の個数
• 'w' → two（2）の個数
• 'g' → eight（8）の個数
• 'x' → six（6）の個数

ステップ2：確定済みの数字を引いて求める数字

続く4つの数字は、ほかの数字と共有している文字をちょうど1つだけ含みます。先に確定した数字の分を差し引けば求まります。

• 's' → seven（7）：総出現数から six（6）の分を引く
• 'v' → five（5）：総出現数から seven（7）の分を引く
• 'f' → four（4）：総出現数から five（5）の分を引く
• 'h' → three（3）：総出現数から eight（8）の分を引く

ステップ3：複数の数字にまたがる文字で求める残り

最後に残る2つの数字は、対応する文字が複数の数字にまたがっています。関連する数字をすべて差し引きましょう。

• 'o' → one（1）：総出現数から（zero ＋ two ＋ four）の分を引く
• 'i' → nine（9）：総出現数から（five ＋ six ＋ eight）の分を引く

ステップ4：結果の文字列を組み立てる

すべての数字の個数が確定したら、0から9の順に、その個数だけ該当する数字の文字を結果文字列 ans に追加していきます。最後に ans を返せば完成です。

C++による実装例

理解を深めるために、実際のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    string originalDigits(string s) {
        string nums[]= {"zero", "one", "two", "three", "four", "five", "six", "seven","eight", "nine"};
        vector <int> cnt(10);
        string ans = "";
        int n = s.size();
        for(int i = 0; i < n; i++){
            if(s[i] == 'z')cnt[0]++;
            if(s[i] == 'w') cnt[2]++;
            if(s[i] == 'g')cnt[8]++;
            if(s[i] == 'x')cnt[6]++;
            if(s[i] == 'v')cnt[5]++;
            if(s[i] == 'o')cnt[1]++;
            if(s[i] == 's')cnt[7]++;
            if(s[i] == 'f')cnt[4]++;
            if(s[i] == 'h')cnt[3]++;
            if(s[i] == 'i') cnt[9]++;
        }
        cnt[7] -= cnt[6];
        cnt[5] -= cnt[7];
        cnt[4] -= cnt[5];
        cnt[1] -= (cnt[2] + cnt[4] + cnt[0]);
        cnt[3] -= cnt[8];
        cnt[9] -= (cnt[5] + cnt[6] + cnt[8]);
        for(int i = 0; i < 10; i++){
            for(int j = 0; j < cnt[i]; j++){
                ans += (char)(i + '0');
            }
        }
        return ans;
    }
};
main(){
    Solution ob;
    cout << ob.originalDigits("fviefuro");
}

実行結果

入力

"fviefuro"

出力

"45"

計算量の評価

このアルゴリズムは文字列を一度走査するだけで済むため、時間計算量は O(n) です。また、追加で必要なメモリは固定長のカウント配列のみなので、空間計算量は O(1) となります。入力長が最大50,000文字であっても、十分高速に動作するのが大きな魅力です。