アルゴリズム概要

💡 この問題を一言で言うと：「複数の文字列を先頭から見比べて、全員に共通する最長の接頭辞を取り出す問題」です。

文字列の配列 strs が与えられたとき、すべての文字列に共通する最長の接頭辞（先頭部分）を返します。 共通する接頭辞が1文字も無ければ、空文字列 "" を返します。

⚠️ なぜ単純な方法では解けないのか

  • 共通接頭辞の長さは、文字列の本数が増えるほど短くなっていく可能性があるため、候補をどう縮めていくかを丁寧に管理する必要があります。
  • 空文字列や要素数1件などの境界的な入力（エッジケース）を見落とすと、実装が一見正しく動いているように見えても、特定の入力でだけ誤った結果を返してしまいます。
O(S)
時間計算量
O(1)
空間計算量
最大200件 各200文字
入力サイズの制約
水平走査
採用アプローチ

入出力例

例1

strs = [flower, flow, flight]

出力: fl

なぜ正解か：3つの文字列すべてが f と l で始まっており、3文字目でそれぞれ o / o / i と分かれるため、 共通しているのは先頭2文字の fl までです。

例2

strs = [dog, racecar, car]

出力: （空文字列）

なぜ正解か：dog, racecar, car はそもそも先頭の1文字目からすべて異なる（d, r, c）ため、 共通する接頭辞は1文字も存在しません。

ステップバイステップ解説

代表例 strs = [flower, flow, flight] を使って、水平走査アルゴリズムがどのように動くかを1ステップずつ確認しましょう。 左のリストからステップを選ぶか、「再生」ボタンで自動的に進めることができます。

実装（Python / TypeScript / Go / Rust）

同じアルゴリズムでも、言語によって書き方や最適化の方向性が変わります。 タブを切り替えて、4言語それぞれの実装・動作トレース・言語特有のポイントを見比べてみましょう。

処理フローチャート

計算量分析

📖 Big-O 記法の読み方

O(1)
入力サイズに関わらず
常に一定の速さ
O(n)
入力が2倍になると
処理も約2倍
O(S)
全文字数Sに
比例して増加
O(n²)
入力が2倍になると
処理は約4倍
言語 採用アルゴリズム 時間計算量 空間計算量 候補の縮め方
Python 垂直走査（zip + set） O(S) O(1) 一致した文字をリストに集め join で結合
TypeScript 水平走査（startsWith） O(S) O(1) slice で新しい文字列に再代入
Go 水平走査（strings.HasPrefix） O(S) O(1) スライス式でコピーせず範囲だけ変更
Rust 水平走査（starts_with） O(S) O(1) usize の長さのみ更新し文字列は最後に1回だけ生成

🔍 なぜこの計算量になるのか

どの言語の実装も、最悪の場合で全文字列の全文字を最大1回ずつ調べる構造になっているため、時間計算量は O(S)（Sは全文字列の合計文字数）です。 空間計算量については、候補の文字列（または候補の長さを表す整数）以外に追加のデータ構造を使わないため、出力用の文字列を除けば O(1) になります。

言語間比較

同じアルゴリズムでも、言語ごとに「メモリの扱い方」や「エラーの表現方法」が異なります。 ここでは4言語の実装を横並びで比較し、それぞれの言語特有の設計判断を振り返ります。

観点 Python TypeScript Go Rust
メモリ確保の特徴 join で最後に1回だけ結合 slice のたびに新しい文字列 スライス式はコピーなし 整数更新のみ、最後に1回だけ確保
エラー表現 TypeError / ValueError の例外 TypeError / RangeError の例外 error 戻り値（提出版は省略） Result型が定石だが戻り値固定のため空文字列で表現
メモリ管理方式 GC（ガベージコレクション） GC（ガベージコレクション） GC（ガベージコレクション） 所有権システム（GC不要）
型安全性の担保方法 型ヒント + pylance readonly + 型ガード 明示的な型宣言 + go vet 所有権システム + コンパイラチェック

相違点の背景

Python・TypeScript・GoはGC（ガベージコレクション、＝使い終わったメモリを自動で回収する仕組み）付きの言語であるため、 文字列の縮小操作で新しいオブジェクトが生成されてもGCが後始末をしてくれます。 一方Rustにはガベージコレクタが無く、コンパイル時に所有権を追跡する仕組みがあるため、 「新しい文字列を作らず整数だけを更新する」という、より低レベルなメモリ効率を意識した設計が自然に選ばれます。

📖 用語集

このページで登場した専門用語をまとめました。分からない言葉が出てきたときに参照してください。

▶ イミュータブル
一度作成したら内容を変更できない性質のことです。Python・TypeScript（JavaScript）・Go・Rustのいずれの言語でも文字列はイミュータブルであり、 「候補を1文字縮める」処理は実際には新しい範囲を指す文字列（またはスライス）を作り直していることになります。
▶ インデックスエラー
配列や文字列の範囲外の要素にアクセスしようとしたときに発生するエラーです。 例えば空の配列に対して strs[0] にアクセスすると発生する可能性があるため、多くの実装で最初に空配列のチェックを行います。
▶ エッジケース
空の配列・要素数1件・全要素が完全一致など、通常とは異なる境界的な条件の入力のことです。 エッジケースを見落とすと、普通のテストは通るのに特定の入力でだけバグが発生することがあります。
▶ 型ヒント
関数の引数や戻り値に型を注釈として書く仕組みです。Pythonでは List[str] のように書き、pylance（VSCodeの型チェッカー）が実行前に型の誤りを検出できるようにします。
▶ 計算量
入力の大きさに対して、処理にかかる手間（時間計算量）や使用するメモリ量（空間計算量）がどう増えるかの目安です。 Big-O記法（O(n) など）で表され、この問題では時間計算量 O(S)、空間計算量 O(1) になります。
▶ 借用
Rust特有の仕組みで、値の所有権を渡さずにその値を参照することです。 &str のように書くことで、Vec<String> の所有権を保持したまま中身を安全に読み取れます。
▶ 垂直走査
複数の文字列を「同じ位置（インデックス）」ごとに縦方向に比較していく方法です。 Pythonの実装では zip と set という組み込み関数を組み合わせてこの走査を実現しています。
▶ 水平走査
1つの文字列（先頭の文字列）を基準の候補として、他の文字列と丸ごと比較しながら候補を縮めていく方法です。 TypeScript・Go・Rustの実装ではこちらを採用しています。
▶ スライス
文字列や配列の一部分（範囲）だけを、コピーを作らずに参照する操作です。 Go の s[:i] や Rust の &s[..n] がこれにあたります。
▶ 早期終了
それ以上調べても答えが変わらないと分かった時点で処理を打ち切ることです。 この問題では候補が空文字列になった時点で、共通接頭辞が無いと確定するため即座に処理を終えます。
▶ 所有権
値を"誰が管理するか"をコンパイル時に決めるRust独自の仕組みです。 ガベージコレクタを使わずにメモリを安全に管理できる一方、値を渡す際に「借用」か「移動」かを意識する必要があります。
▶ パニック
GoやRustで回復不能なエラーが発生した際に起きる強制終了です。 範囲外のインデックスやスライスへアクセスしようとした場合などに発生することがあるため、事前の入力検証が重要になります。