Algorithm Language Agnostic Reverse Puzzle

文字配列内の単語の順序を効率的に逆転する

文字配列内の単語の順序を逆転することは、アルゴリズムや文字列操作の理解を試す古典的な問題です。面接の準備をしている場合でも、プログラミングスキルを磨いている場合でも、この課題を習得することは非常に有意義です。この投稿では、問題を詳しく探り、C/C++で効率的な解決策を分解していきます。

問題

文を形成する文字の配列が与えられたとき、単語の順序を逆転し、単語内の個々の文字を変更しないことが目標です。例えば、入力が次のような場合：

"this is a string"

出力は次のようになるべきです：

'string a is this'

この課題では、この操作をO(N)の時間とO(1)の空間で達成する必要があるため、split()のような関数や追加の空間を操作するスタックのようなデータ構造を使用することはできません。

問題の分析

時間計算量

O(N)の時間計算量が求められるということは、アルゴリズムがデータを線形に走査しなければならないことを意味します。したがって、時間計算量を増加させるネストされたループは避けるべきです。

空間計算量

O(1)の空間計算量のためには、ストレージ用に追加のデータ構造を使用できません。これは、操作が入力配列内で直接行われる必要があることを意味します。

解決策

この問題を効率的に解決するために、ソリューションを段階的に分解していきましょう。私たちは2パスアプローチを利用します。

ステップ1：全体の文字列を逆転する

最初のステップは、配列全体を逆転することです。これにより、元の文字列はすべての文字が逆転された文字列に変わります。たとえば、元の "this is a string" は逆転後：

"gnirts a si siht"

ステップ2：各単語を逆転する

全体の文字列を逆転したので、今度は各単語を逆転して正しい順序に戻す必要があります。次に、C/C++でこれらのステップを実装する方法を示します：

void swap(char* str, int i, int j) {
    char t = str[i];
    str[i] = str[j];
    str[j] = t;
}

void reverse_string(char* str, int length) {
    for(int i = 0; i < length / 2; i++) {
        swap(str, i, length - i - 1);
    }
}

void reverse_words(char* str) {
    int l = strlen(str);
    // 文字列全体を逆転
    reverse_string(str, strlen(str));
    int p = 0;
 
    // 単語の境界を見つけ、単語ごとに逆転
    for(int i = 0; i < l; i++) {
        if(str[i] == ' ') {
            reverse_string(&str[p], i - p);  // 識別した単語を逆転
            p = i + 1;
        }
    }
    // 最後の単語を逆転
    reverse_string(&str[p], l - p);
}

コードの説明

スワップ関数: 配列内の文字を入れ替えるためにヘルパー関数swapを使用します。
逆転文字列関数: この関数はスワップ関数を使用して文字列の文字を逆転します。
単語を逆転する関数: コア関数はまず文字配列全体を逆転し、その後、スペースで識別された個々の単語を逆転するために反復処理します。最後の単語はループが終了した後に処理されます。

計算量分析

配列を2回逆転することで、時間計算量はO(N)になります。

最初のパス：O(N)で全体の文字列を逆転。
2回目のパス：O(N)で各単語を逆転。

したがって、最終的な時間計算量はO(N)のままです。空間計算量はO(1)であり、反復用の変数を除いて追加の空間は利用していません。

結論

文字配列内の単語の順序を効率的に逆転するには、文字列操作の組み合わせとインデックスアクセスの理解が必要です。ここで示したアルゴリズムは、C/C++を使用しながらO(N)の時間とO(1)の空間要件を満たす明確なアプローチを示しています。この解決策を練習すれば、プログラミングツールキットに素晴らしい追加となるでしょう！