0%

LeetCode 5. Longest Palindromic Substring

Posted on Edited on In

题目

原题在此
Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = “babad”
Output: “bab”
Note: “aba” is also a valid answer.

Example 2:

Input: s = “cbbd”
Output: “bb”

Example 3:

Input: s = “a”
Output: “a”

Example 4:

Input: s = “ac”
Output: “a”

Constraints:

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters (lower-case and/or upper-case).

解析

暴力解法

遍历所有可能的字符串,判断是否是回文串并记录长度.可能的优化有:

  • 在子串长度大于已找到的最长字串时再判断是否是回文
  • 长度为1的字串必为回文串无需访问

复杂度分析:对于长度为n的字符串,有$n^2$个字符串待检查(严格来说是$\frac{n(n+1)}{2}$), 每次检查是否为回文的消耗为O(n), 整体时间复杂度为$O(n^3)$. 原地检查不使用额外空间, 空间复杂度为$O(1)$.

动态规划

DP算法根据暴力解法优化而来. 回文串有如下属性: 一个回文串剪去首尾两个字符还是一个回文串.
用bool dp[i][j]记录字串s[i..j] // 闭区间, 包括i和j是否为回文串
根据回文串属性, 有状态转移方程dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1]
边界条件既是长度为1的字串是回文串 -> dp[][]数组对角线全为true.

复杂度分析:对于长度为n的字符串,有$n^2$个dp状态,每次状态转移的时间为$O(1)$, 整体时间复杂度为$O(n^2)$. 空间复杂度即为存储dp状态所需的大小, $O(n^2)$.

中心扩散

中心扩散的思想和DP检查回文串的思路相反, 是以每一或两个字符为对称轴(回文串的奇偶,”aba”,”abba”)检查两侧最多有几个字符相同.
复杂度分析:对于长度为n的字符串, 有n个奇数回文中心和n-1个偶数回文中心, 每次检查消耗为$O(n)$, 整体时间复杂度为$O(n^2)$. 空间复杂度为$O(1).

Manacher

这个是个线性时间复杂度的算法, 光靠文字和公式理解起来比较抽象, 建议看视频讲解.

代码

暴力(java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        int maxLen = 1;
        int begin = 0;
        
        char[] charArr = s.toCharArray();
        for (int i = 0; i < len - 1; ++i) {
            for (int j = i + 1; j < len; ++j) {
                if(j - i + 1 > maxLen && isPalindrome(charArr, i, j)) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
    
    private boolean isPalindrome(char[] charArr, int i, int j) {
        while (i < j) {
            if (charArr[i] != charArr[j]) return false;
            i++;
            j--;
        }
        return true;
    }
}

DP(golang)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func longestPalindrome(s string) string {
    size, maxLen, begin := len(s), 1, 0
    dp := make([][]bool, size)
    for i := 0; i < size; i++ {
        dp[i] = make([]bool, size)
        dp[i][i] = true
    }
    
    for j := 1; j < size; j++ {
        for i := 0; i < j; i++ {
            if(s[i] != s[j]) {
                dp[i][j] = false
            } else {
                if (j - i < 3) {
                    dp[i][j] = true
                } else {
                    dp[i][j] = dp[i + 1][j - 1]
                }
            }
            
            if(dp[i][j] && j - i + 1 > maxLen) {
                maxLen = j - i + 1
                begin = i
            }
        }
    }
    return s[begin: begin + maxLen]
}

中心扩散(golang)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Using global variables will cause inconsistent result between "Run" and "Submit"
func longestPalindrome(s string) string {
    var size, maxLen, begin int = len(s), 1, 0
    for i := 0; i < size - 1; i++ {
        begin, maxLen = isPalindrome(s, i, i, begin, maxLen)
        begin, maxLen = isPalindrome(s, i, i + 1, begin, maxLen)
    }
    return s[begin: begin + maxLen]
}

func isPalindrome(s string, i, j, begin, maxLen int) (int, int) {
    size := len(s)
    for i >= 0 && j < size && s[i] == s[j] {
        i--
        j++
    }
    if j - i - 1 > maxLen {
        begin = i + 1
        maxLen = j - i - 1
    }
    return begin, maxLen
}

Manacher(golang)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
func longestPalindrome(s string) string {
    var maxLen, begin, maxRight, center int = 1, 0, 0, 0
    tmp := make([]rune, 0)
	tmp = append(tmp, '#')
	for _, c := range s {
		tmp = append(tmp, c)
		tmp = append(tmp, '#')
	}
    tsize := len(tmp)
    dp := make([]int, tsize)
    for i := 0; i < tsize; i++ {
        if i < maxRight {
            mirror := 2 * center - i;
            dp[i] = min(maxRight - i, dp[mirror])
        }
        
        left, right := i - (dp[i] + 1), i + (dp[i] + 1)
        for left >= 0 && right < tsize && tmp[left] == tmp[right] {
            dp[i]++
            left--
            right++
        }
        
        if i + dp[i] > maxRight {
            center, maxRight = i, dp[i] + i
        }
        
        if dp[i] > maxLen {
            maxLen = dp[i]
            begin = (i - maxLen) / 2
        }
    }
    return s[begin: begin + maxLen]
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}