【Swift / LeetCode】中心展開法（最長回文文字列を求める）｜5. Longest Palindromic Substring

試したこと

• sとs.reversed()を１文字ずつ比較することでうまく作れないかなあと思ってまずはコードを書いてみた

class Solution {
    func longestPalindrome(_ s: String) -> String {
        let n = s.count
        let Sa = Array(s)
        let Sr = Array(s).reversed()
        var i = 0

        while i <= n {
            let target = Sa[i]
            for j in 0 ..< n {
                //　比較するロジック
            }
            i += 1
        }
    }
}

• しかしこの場合だと、下記のようなケースだと間違った回答を生み出してしまう。

// s.abacdとs.reversedのabacdは回文ではない
s = "abacdfgdcaba"
reversed = "abacdgfdcaba"

コード

class Solution {
    func longestPalindrome(_ s: String) -> String {
        let Sa = Array(s)
        let n = Sa.count
        if n < 2 { return s }

        var start = 0
        var maxLen = 1
        var i = 0

        func expand(_ left: Int, _ right: Int) {
            var l = left
            var r = right

            while l >= 0 && r < n && Sa[l] == Sa[r] {
                let len = r - l + 1
                if len > maxLen {
                    start = l
                    maxLen = len
                }
                l -= 1
                r += 1
            }
        }

        while i < n {
            expand(i, i)
            expand(i, i + 1)
            i += 1
        }

        let startIndex = s.index(s.startIndex, offsetBy: start)
        let endIndex = s.index(startIndex, offsetBy: maxLen)
        return String(s[startIndex..<endIndex])
    }
}

必要な変数

• Sa ... 文字列Saを配列に変換する
• n ... Saの配列の要素数
• start ... 最初のインデックス
• maxLen ... 最長列
• i ... for用のインデックス

実装方針

1. 変数の定義

        let Sa = Array(s)
        let n = Sa.count
        var start = 0
        var maxLen = 1
        var i = 0

1-1. Point

if n < 2 { return s }

• 1文字もしくは""の場合はその時点で回文になるため文字列をそのまま返す。

2. 大小比較と配列のマージ

2-1. 内部関数の定義

• 引数left ... 二分探索の左辺を定義する
• 引数right ... 二分探索の右辺を定義する

func expand(_ left: Int, _ right: Int) {}

2-2. 現在の文字が回文状態か確認する

• leftとrightが一致している限り、範囲を広げ続ける

while l >= 0 && r < n && Sa[l] == Sa[r] {}

2-3. 現在の文字が回文状態か確認する

• 内部関数expandの中で
  • lenの中に現在の文字列の長さを代入する
  • maxLenとlenを比較して最長の長さを更新しそうであれば
    • startに開始地点lと、maxLenに終了地点lenを代入する
  • 現在の文字から左右に１ずつ探索範囲を伸ばす

let len = r - l + 1
if len > maxLen {
    start = l
    maxLen = len
}
l -= 1
r += 1

3. 偶奇判定

• iがnを超えないか判定する

while i < n {}

• i文字目の回文判定を行う。

expand(i, i) // 最長回文文字列が奇数の時の判定　"aba", "ababa", "shorirohs"など
expand(i, i + 1) // 最長回文文字列が偶数の時の判定　"abba", "abccba", "abcddcba"など

• iのインデックスを更新する

謝辞