# 题目描述

• `1 <= s.length <= 1000`
• `s` 仅由数字和英文字母（大写和/或小写）组成

# 朴素解法

• 回文串长度是奇数，则依次判断 `s[i − k] == s[i + k], k = 1,2,3…`

• 回文串长度是偶数，则依次判断 `s[i − k] == s[i + k − 1], k = 1,2,3…`

``class Solution {public String longestPalindrome(String s) {String ans = "";for (int i = 0; i < s.length(); i++) {// 回文串为奇数int l = i - 1, r = i + 1;String sub = getString(s, l, r);if (sub.length() > ans.length()) ans = sub;// 回文串为偶数l = i - 1;r = i + 1 - 1;sub = getString(s, l, r);if (sub.length() > ans.length()) ans = sub;}return ans;}String getString(String s, int l, int r) {while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {l--;r++;}return s.substring(l + 1, r);}``}``

# Manacher 算法

Manacher 确实是「回文串」问题的最优解。

Manacher 算法较长，为了避免回文串长度奇偶问题的分情况讨论，我会对原字符进行处理，在边界和字符之间插入占位符。

``class Solution {public String longestPalindrome(String s) {if (s.length() == 1) return s;char[] chars = manacherString(s);int n = chars.length;int[] pArr = new int[n];int C = -1, R = -1, pos = -1;int max = Integer.MIN_VALUE;for (int i = 0; i < n; i++) {pArr[i] = i < R ? Math.min(pArr[C * 2 - i], R - i) : 1;while (i + pArr[i] < n && i - pArr[i] > -1) {if (chars[i + pArr[i]] == chars[i - pArr[i]]) {pArr[i]++;} else {break;}}if (i + pArr[i] > R) {R = i + pArr[i];C = i;}if (pArr[i] > max) {max = pArr[i];pos = i;}}int offset = pArr[pos];StringBuilder sb = new StringBuilder();for (int i = pos - offset + 1; i <= pos + offset - 1; i++) {if (chars[i] != '#') sb.append(chars[i]);}return sb.toString();}char[] manacherString(String s) {char[] chars = new char[s.length() * 2 + 1];for (int i = 0, idx = 0; i < chars.length; i++) {chars[i] = (i & 1) == 0 ? '#' : s.charAt(idx++);}return chars;}``}``

1 声望

0 粉丝

0 条评论

# 题目描述

• `1 <= s.length <= 1000`
• `s` 仅由数字和英文字母（大写和/或小写）组成

# 朴素解法

• 回文串长度是奇数，则依次判断 `s[i − k] == s[i + k], k = 1,2,3…`

• 回文串长度是偶数，则依次判断 `s[i − k] == s[i + k − 1], k = 1,2,3…`

``class Solution {public String longestPalindrome(String s) {String ans = "";for (int i = 0; i < s.length(); i++) {// 回文串为奇数int l = i - 1, r = i + 1;String sub = getString(s, l, r);if (sub.length() > ans.length()) ans = sub;// 回文串为偶数l = i - 1;r = i + 1 - 1;sub = getString(s, l, r);if (sub.length() > ans.length()) ans = sub;}return ans;}String getString(String s, int l, int r) {while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {l--;r++;}return s.substring(l + 1, r);}``}``

# Manacher 算法

Manacher 确实是「回文串」问题的最优解。

Manacher 算法较长，为了避免回文串长度奇偶问题的分情况讨论，我会对原字符进行处理，在边界和字符之间插入占位符。

``class Solution {public String longestPalindrome(String s) {if (s.length() == 1) return s;char[] chars = manacherString(s);int n = chars.length;int[] pArr = new int[n];int C = -1, R = -1, pos = -1;int max = Integer.MIN_VALUE;for (int i = 0; i < n; i++) {pArr[i] = i < R ? Math.min(pArr[C * 2 - i], R - i) : 1;while (i + pArr[i] < n && i - pArr[i] > -1) {if (chars[i + pArr[i]] == chars[i - pArr[i]]) {pArr[i]++;} else {break;}}if (i + pArr[i] > R) {R = i + pArr[i];C = i;}if (pArr[i] > max) {max = pArr[i];pos = i;}}int offset = pArr[pos];StringBuilder sb = new StringBuilder();for (int i = pos - offset + 1; i <= pos + offset - 1; i++) {if (chars[i] != '#') sb.append(chars[i]);}return sb.toString();}char[] manacherString(String s) {char[] chars = new char[s.length() * 2 + 1];for (int i = 0, idx = 0; i < chars.length; i++) {chars[i] = (i & 1) == 0 ? '#' : s.charAt(idx++);}return chars;}``}``