5.最长回文子串
5.最长回文子串
题解
题目：给你一个字符串 s，找到 s 中最长的回文子串
思路：
- 暴力，两重循环，第一层循环i作为起始，第二层循环j作为结束，判断字符串i到j是否是回文串
- 中心扩散，遍历字符串，以中心作为回文串中心，判断中心的两边，进行扩散
- dp，dp[i][j]为以i开始j结尾的字符串，如果s[i]==s[j]，那么dp[i][j]=dp[i+1][j-1]，这就是状态转移了，首先要枚举字串长度，再枚举左边界，如果反过来则有些状态是还没有确定的
- 马拉车算法，O(n)的复杂度，不搞竞赛学这个没什么意义，不写了
代码
//暴力 func longestPalindrome(s string) string { n := len(s) maxLen := 0 ans := "" for i := 0; i < n; i++ { for j := i; j < n; j++ { if check(i, j, s) { if j-i+1 > maxLen { maxLen = j - i + 1 ans = s[i : j+1] } } } } return ans } func check(l, r int, s string) bool { for ; l <= r; l, r = l+1, r-1 { if s[l] != s[r] { return false } } return true }
//中心扩散 func longestPalindrome(s string) string { n := len(s) maxLen := 0 ans := "" for i := 0; i < n; i++ { if cnt, ok := check1(i, s); ok { if cnt > maxLen { maxLen = cnt ans = s[i-(cnt-1)/2 : i+(cnt-1)/2+1] } } if cnt, ok := check2(i, i+1, s); ok { if cnt > maxLen { maxLen = cnt ans = s[i-(cnt-1)/2 : i+(cnt-1)/2+2] } } } return ans } func check1(l int, s string) (int, bool) { long := 0 for i, j := l, l; i >= 0 && j < len(s); i, j = i-1, j+1 { if s[i] != s[j] { return long, true } long = j - i + 1 } return long, true } func check2(l, r int, s string) (int, bool) { long := 0 for i, j := l, r; i >= 0 && j < len(s); i, j = i-1, j+1 { if s[i] != s[j] { return long, true } long = j - i + 1 } return long, true }
//dp func longestPalindrome(s string) string { n := len(s) // dp[i][j] 表示 s[i..j] 是否是回文串 dp := make([][]bool, n) result := s[0:1] for i := 0; i < n; i++ { dp[i] = make([]bool, n) //所有长度为 1 的子串都是回文串 dp[i][i] = true } //枚举子串长度 for length := 2; length <= n; length++ { // 枚举左边界 for i := 0; i < n; i++ { //确定右边界 j := i + length - 1 if j >= n { break } if s[i] == s[j] { if length <= 2 { dp[i][j] = true } else { dp[i][j] = dp[i+1][j-1] } } else { dp[i][j] = false } //dp[i][j] == true 成立，就表示子串 s[i..j] 是回文 if dp[i][j] == true && j-i+1 > len(result) { result = s[i : j+1] } } } return result }
