0005.最长回文子串

https://leetcode.cn/problems/longest-palindromic-substring/

方法一：动态规划

时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$。

func longestPalindrome(s string) string {
	dp, n, ans := make([][]bool, len(s)), len(s), s[:1]
	for i := 0; i < n; i++ {
		dp[i] = make([]bool, n)
		dp[i][i] = true
	}
	for end := 1; end < n; end++ {
		for start := 0; start < end; start++ {
			if s[start] == s[end] && (end-start == 1 || dp[start+1][end-1]) {
				dp[start][end] = true
				if end-start+1 > len(ans) {
					ans = s[start : end+1]
				}
			}
		}
	}
	return ans
}

impl Solution {
    pub fn longest_palindrome(s: String) -> String {
        let n = s.len();
        let mut dp = vec![vec![false; n]; n];
        let mut ans = "".to_string();
        let arrays = s.as_bytes();

        for end in 0..n {
            for start in 0..=end {
                let (a, b) = (arrays[start], arrays[end]);
                if a == b && (end - start <= 2 || dp[start + 1][end - 1]) {
                    dp[start][end] = true;
                    if end - start + 1 > ans.len() {
                        ans = s.get(start..end + 1).unwrap().to_string();
                    }
                }
            }
        }
        ans
    }
}

方法二：中心扩展算法

时间复杂度 $O(n^2)$，空间复杂度 $O(1)$。

func palindrome(s string, i, j int) string {
	for i >= 0 && j < len(s) {
		if s[i] == s[j] {
			i, j = i-1, j+1
		} else {
			break
		}
	}
	return s[i+1 : j]
}

func longestPalindrome(s string) string {
	n, ans := len(s), s[:1]
	for i := 0; i < n; i++ {
		r1, r2 := palindrome(s, i, i), palindrome(s, i, i+1)
		if len(r1) > len(ans) {
			ans = r1
		}
		if len(r2) > len(ans) {
			ans = r2
		}
	}
	return ans
}