Zenn
🪞

JavaScriptで解くLeetCode：Longest Palindromic Substring

2025/01/02に公開
LeetCode
javescript
tech

このシリーズでは、プログラミング学習サイト LeetCode に掲載されている問題の中から良問を厳選し、JavaScript を使って解説します。

今回は、Arai60に収録されている「Longest Palindromic Substring（最長の回文部分文字列を探す）」の問題を解説します。

Palindromic は、回文ですね。しんぶんし：上から読んでも「しんぶんし」、下から読んでも「しんぶんし」。

この問題では、入力文字列の中で最も長い回文（前から読んでも後ろから読んでも同じ文字列）を返すことが求められます。

では、コードの各部分を詳しく解説していきます。

問題の要件

入力

  • 文字列 s（長さ1以上1000以下、英数字のみ）

出力

  • 入力文字列の中で最も長い回文部分文字列

例

  1. 入力: "babad"
    出力: "bab" または "aba"

  2. 入力: "cbbd"
    出力: "bb"

コードの解説

全体の構造

var longestPalindrome = function(s) {
    if (s.length < 2) return s;
    
    let start = 0;
    let maxLength = 1;

    function expandAroundCenter(left, right) { ... }
    
    for (let i = 0; i < s.length; i++) { ... }

    return s.substring(start, start + maxLength);
};

  1. 初期条件の処理

    • 入力文字列の長さが2未満の場合、回文探索を行わず文字列をそのまま返します。
    if (s.length < 2) return s;

  2. 変数の初期化

    • start: 最長回文部分文字列の開始位置を保持。
    • maxLength: 最長回文部分文字列の長さを保持。
    let start = 0;
let maxLength = 1;

  3. 補助関数 expandAroundCenter

    • 回文の中心を左右に拡張するロジックを実装しています。
    • 入力:
      • left（中心の左側のインデックス）
      • right（中心の右側のインデックス）
    • 処理内容:
      • 左右の文字が一致している間、範囲を広げて回文の長さを更新。
    function expandAroundCenter(left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
        const currentLength = right - left + 1;
        if (currentLength > maxLength) {
            start = left;
            maxLength = currentLength;
        }
        left--;
        right++;
    }
}

  4. 全文字を中心として探索

    • 各文字を中心にして奇数長の回文を探索。
    • 文字間を中心として偶数長の回文を探索。
    for (let i = 0; i < s.length; i++) {
    expandAroundCenter(i, i);     // 奇数長の回文
    expandAroundCenter(i, i + 1); // 偶数長の回文
}

  5. 最終結果を返す

    • start から start + maxLength の範囲を抜き出し、最長回文部分文字列を返します。
    return s.substring(start, start + maxLength);

コードのポイント

  1. 回文の中心を拡張するアイデア

    • 回文は「中心」を基準に左右対称である性質を持っています。この性質を利用して、すべての文字を中心として探索することで、最長回文を見つけます。
    • 時間計算量は (O(n^2))、空間計算量は (O(1)) です。

  2. 奇数長と偶数長の回文を区別

    • 回文の長さが奇数の場合、中心は1文字。
    • 回文の長さが偶数の場合、中心は2文字間。

例を使った動作説明

入力: "babad"

  1. 初期状態

    • start = 0
    • maxLength = 1

  2. 探索開始

    • i = 0: 奇数回文 → "b"、偶数回文 → 空
    • i = 1: 奇数回文 → "bab"、偶数回文 → 空
    • i = 2: 奇数回文 → "aba"、偶数回文 → 空
    • i = 3: 奇数回文 → "a"、偶数回文 → 空
    • i = 4: 奇数回文 → "d"、偶数回文 → 空

  3. 結果

    • 最長回文は "bab" または "aba"。

応用と改良

  • 時間効率を上げる方法
    • 動的計画法（Dynamic Programming）を用いれば、時間計算量を (O(n^2)) に保ちながら空間計算量を減らす工夫が可能です。
  • 文字列の長さが大きい場合
    • (O(n)) の解法として「Manacher's Algorithm」を使用すると効率的です。

このコードはシンプルで理解しやすい一方、効率をさらに高める余地もあります。

まずは「回文の中心を拡張する」という考え方を実装してみてください。

では See you later, alligator!

Discussion