攻城獅
Not a programmer 不工程的攻城獅

Not a programmer 不工程的攻城獅

LeetCode Solution, Medium, 5. Longest Palindromic Substring

找出最長的回文子字串

攻城獅's photo
攻城獅
·Jul 10, 2022·

Subscribe to my newsletter and never miss my upcoming articles

Play this article

5. Longest Palindromic Substring

題目敘述

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints:

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters.

Hint 1:

How can we reuse a previously computed palindrome to compute a larger palindrome?

Hint 2:

If “aba” is a palindrome, is “xabax” a palindrome? Similarly is “xabay” a palindrome?

Hint 3:

Complexity based hint: If we use brute-force and check whether for every start and end position a substring is a palindrome we have O(n^2) start - end pairs and O(n) palindromic checks. Can we reduce the time for palindromic checks to O(1) by reusing some previous computation?

題目翻譯

提供一個字串 s,從中找出最長的回文子字串。有沒有可能利用先前的條件,讓時間複雜度變成 O(n) 呢?

解法解析

這題如果不考慮將時間複雜度降到 O(n) 的話難度的確只有 Medium 吧,但是一但考量到複雜度整個就是 Hard 等級了,因為就會需要使用到所謂的馬拉車算法 (Manacher's Algorithm)。如果不考慮的話,大多就會使用了中心擴展法來解個題目。

解法範例

Go

Expand Around Center
func longestPalindrome(s string) string {
    if len(s) < 2 {
        return s
    }
    start, end := 0, 0
    for i := 0; i < len(s); i++ {
        len1 := expandAroundCounter(s, i, i)
        len2 := expandAroundCounter(s, i, i+1)
        var length int = len2
        if len1 > len2 {
            length = len1
        }
        if length > end-start {
            start = i - (length-1)/2
            end = i + length/2
        }
    }
    return s[start : end+1]
}

func expandAroundCounter(s string, left int, right int) int {
    for left >= 0 && right < len(s) && s[left] == s[right] {
        left--
        right++
    }
    return right - left - 1
}
Manacher's Algorithm
func longestPalindrome(s string) string {
    var expandStr string = "#"
    for _, c := range s {
        expandStr += string(c) + "#"
    }
    var maxLen int = len(expandStr)
    var P []int = make([]int, maxLen)
    var center int = 0
    var right int = 0
    for i := 0; i < maxLen; i++ {
        var mirror int = 2*center - i
        if mirror < 0 {
            mirror = 0
        }
        if right > i {
            P[i] = P[mirror]
            if P[mirror] > right-i {
                P[i] = right - i
            }
        }
        for i-P[i] >= 0 && i+P[i] < maxLen && expandStr[i-P[i]] == expandStr[i+P[i]] {
            P[i]++
        }
        if i+P[i] > right {
            center = i
            right = i + P[i]
        }
    }
    var maxIndex int = 0
    for i, v := range P {
        if v > P[maxIndex] {
            maxIndex = i
        }
    }
    var start int = (maxIndex - P[maxIndex] + 1) / 2
    return s[start : start+P[maxIndex]-1]
}

JavaScript

Expand Around Center
/**
 * @param {string} s
 * @return {string}
 */

var longestPalindrome = function (s) {
    if (s.length === 0) return '';
    else if (s === s.split('').reverse().join('')) return s;
    let start = 0,
        end = 0;
    for (let i = 0; i < s.length; i++) {
        const len1 = expandAroundCenter(s, i, i);
        const len2 = expandAroundCenter(s, i, i + 1);
        const length = Math.max(len1, len2);
        if (length > end - start) {
            start = i - Math.floor((length - 1) / 2);
            end = i + Math.floor(length / 2);
        }
    }
    return s.slice(start, end + 1);
};

const expandAroundCenter = (s, left, right) => {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
        left--;
        right++;
    }
    return right - left - 1;
};
Manacher's Algorithm
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
    if (!s || !s.length) return '';
    const str = `#${s.split('').join('#')}#`;
    const n = str.length;
    let center = 0,
        radius = 0;
    const P = new Array(n).fill(0);

    for (let i = 0; i < n; i++) {
        if (i > radius) {
            P[i] = 1;
        } else {
            const i_mirror = 2 * center - i > 0 ? 2 * center - i : 0;
            P[i] = Math.min(P[i_mirror], radius - i);
        }
        let lo = i - P[i],
            hi = i + P[i];
        while (lo >= 0 && hi < n && str[lo] === str[hi]) {
            lo--, hi++;
        }
        P[i] = hi - i;

        if (i + P[i] > radius) {
            center = i;
            radius = i + P[i];
        }
    }
    const maxLen = Math.max(...P);
    const centerIndex = P.indexOf(maxLen);
    const res = str.substring(centerIndex - maxLen + 1, centerIndex + maxLen);
    return res.split('#').join('');
};

Kotlin


PHP


Python

Expand Around Center
class Solution:
    def longestPalindrome(self, s: str) -> str:
        if s == s[::-1]:
            return s

        start = end = 0
        for i in range(len(s)):
            len1 = self.expandAroundCenter(s, i, i)
            len2 = self.expandAroundCenter(s, i, i + 1)
            length = max(len1, len2)
            if length > end - start:
                start = i - (length - 1) // 2
                end = i + length // 2

        return s[start:end + 1]

    def expandAroundCenter(self, s: str, left: int, right: int) -> int:
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1

        return right - left - 1
Manacher's Algorithm
class Solution:
    def longestPalindrome(self, s: str) -> str:
        T = '#'.join('^{}$'.format(s))
        n = len(T)
        P = [0] * n
        C = R = 0
        for i in range(1, n - 1):
            P[i] = (R > i) and min(R - i, P[2 * C - i])
            while T[i + 1 + P[i]] == T[i - 1 - P[i]]:
                P[i] += 1

            if i + P[i] > R:
                C, R = i, i + P[i]

        max_len, center_idex = max((n, i) for i, n in enumerate(P))
        return s[(center_idex - max_len) // 2: (center_idex + max_len) // 2]

Rust


Swift


Reference

Did you find this article valuable?

Support 攻城獅 by becoming a sponsor. Any amount is appreciated!

Learn more about Hashnode Sponsors
 
Share this