【Java】アルゴリズム徹底解説：文字列を反転させる良い方法・悪い方法（Two Pointerによる最適化）

対象読者

• アルゴリズムの基礎をしっかりと理解したい人
• 配列操作やポインタの考え方を学びたい人
• Javaで効率的なコードを書けるようになりたい人

---

問題

文字配列を引数として受け取り、その順序を反転する関数を作成せよ。
例： s = ['h','e','l','l','o'] → ['o','l','l','e','h']

---

問題の前提条件

• 入力は char[] 型の文字配列とする。

---

解き方パターン1：Brute Force（よくない例）

// 文字列を反転する（非効率な例）
// pre: s = ['h','e','l','l','o']
// post: ['o','l','l','e','h']
public void reverseString(char[] s) {
    // 新しい配列を用意して逆順に格納
    char[] reversed = new char[s.length];
    for (int i = 0; i < s.length; i++) {
        reversed[i] = s[s.length - 1 - i];
    }

    // reversed の内容を s に戻す
    for (int i = 0; i < s.length; i++) {
        s[i] = reversed[i];
    }
}

---

何がいけないのか

1. 余分な配列（reversed）を作成しているため、空間計算量が O(n)
   → 「その場で反転（in-place）」という要件を満たしていない。
   → 後続で紹介するやり方では別の配列を作らずに計算ができます。

2. 2回ループを回しているため、時間計算量も O(2n)
   → 結果的に線形(O(n))ではあるが、後続の最適化された方では1回のループで十分です。

---

解き方パターン2：Two Pointer（良い例）

2つのポインターを利用し、１回のループの中で先頭、最後尾から同時にスキャンをかけて行きます。

class Solution {
    public void reverseString(char[] s) {
        // 方針：
        // 配列の先頭と末尾から同時にポインタを動かし、左右の要素を交換していく
        int front = 0;
        int last = s.length - 1;

        // 先頭ポインタが末尾より手前にある間、スワップを続ける
        while (front < last) {
            swap(s, front, last);
            front++;
            last--;
        }
    }

    // 要素を入れ替えるヘルパーメソッド
    public void swap(char[] s, int front, int last) {
        char temp = s[front];
        s[front] = s[last];
        s[last] = temp;
    }
}

---

このコードの良い点

• 空間計算量が O(1)
  新しい配列を作成せず、与えられた配列の中で反転処理を完結できる。

• 時間計算量は O(n/2) ≒ O(n)
  配列の半分の回数だけスキャンすればよい。

---

ロジック解説

1. 初期化

   • front = 0（左端）
   • last = s.length - 1（右端）

2. ループ処理

   • 条件： front < last

   • 処理：

     1. s[front] と s[last] を入れ替える
     2. front++（左を右に進める）
     3. last--（右を左に進める）

3. 終了条件

   • front >= last になったら中央で交差するため、全体が反転完了。

---

Two Pointer の概念図

初期状態:   [h, e, l, l, o]
front →  ^               ^
           0             4   last

1回目swap: [o, e, l, l, h]
            ↑           ↑
           1             3

2回目swap: [o, l, l, e, h]
               ↑     ↑
               2     2   ← front == last → 完了

---

まとめ

• Brute Forceでは余計な配列を作り O(n)＋O(n) の無駄な処理が発生する。
• Two Pointerを使えば、O(1)空間・O(n)時間で最適に反転できる。

---

個人的に思うこと

この問題は「アルゴリズムを体で理解する」タイプの典型例だなと感じます笑。
特にTwo Pointerは、配列や文字列操作の最適化で頻出の考え方です。
処理のイメージやポインターが動いていくメンタルモデルをマスターし、最適解で解ける幅を増やしていきましょう