はじめに
プログラミング初学者から中級者まで幅広く挑戦している方が多いLeetCode。
本記事では、その中でも頻出かつ基本的な問題「Longest Common Prefix（最長共通接頭辞）」について、
問題の解説・解法の考え方・Javaによる実装・時間計算量の評価まで丁寧に解説します。
この記事の目的
この記事を読むことで、LongestCommonPrefixの解き方や、startWith, substringの使い方を知ることができます。
Longest Common Prefixとは？
「複数の文字列のうち、共通して先頭に現れる最長の部分の文字列を求める」というのがこの問題の主旨です。
例えば、
Input: ["flower", "flow", "flight"]
Output: "fl"この場合、すべての文字列の最初に "fl" が共通して含まれています。
一方で、
Input: ["dog", "racecar", "car"]
Output: ""このように、先頭に共通する部分がない場合は、空文字列 "" を返します。
問題のポイントと考え方
この問題は、基本的な文字列操作を問うもので、以下のようなスキルが身に付きます
制限がある中で「できるだけ効率的に最長共通接頭辞を求める」ためには、貪欲法（Greedy）のような考え方が有効です。
Javaでの解法
以下に示すのは、先頭の文字列を初期の接頭辞として仮定し、他の文字列と比較して共通部分を短くしていくというアプローチです。
public class Solution {
public static String longestCommonPrefix(String[] strs) {
String prefix = strs[0];
for (int i = 1; i < strs.length; i++) {
while (!strs[i].startsWith(prefix)) {
prefix = prefix.substring(0, prefix.length() - 1);
if (prefix.isEmpty())
return "";
}
}
return prefix;
}
}解説
1. 最初の文字列 strs[0] を「仮の最長共通接頭辞」とします。
2. それ以降の文字列と、先頭から共通しているかを startsWith で判定。
3. 共通していない場合は、substring を使って末尾から1文字ずつ削っていきます。
4. もし共通部分がなくなったら "" を返します。
5. 最後まで処理できれば、それが最長の共通接頭辞です。
時間計算量と空間計算量
時間計算量：O(S)
ここで、S は全ての文字列中の文字数の合計です。
最悪の場合、すべての文字を一度確認する必要があります。
空間計算量：O(1)
追加で使うメモリは、prefix という変数だけで済みます。
なぜこの方法が有効なのか
毎回すべての文字列の共通接頭辞を再計算するよりも、「すでに分かっている共通部分」から削っていくことで、処理を最小限に抑えられます。これはまさに「貪欲法（Greedy）」的な考え方です。
他の解法との比較
他にも、以下のような方法があります：
縦に比較する方法：
各文字列の同じインデックスの文字を順に比較する。
ソートして、最初と最後を比較：
ソート後、最初と最後の文字列の共通部分が全体の最長共通接頭辞となる。
本記事の方法は直感的かつ実装も簡潔で、初学者にもおすすめです。
まとめ
LeetCodeの「Longest Common Prefix」は、文字列の基本操作を学ぶうえで非常に良い問題です。今回のアプローチでは、
という流れで、効率的に解くことができました。
この記事が皆さんの理解の一助になれば幸いです。