概述
算法是一个程序员的核心竞争力，也是面试最重要的考查环节。本文整理一些与回文相关的基础算法题。注：本文语言为Java。
验证回文串
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。给定一个字符串s，如果是回文串，返回true；否则，返回false。
示例输入
输入: s = "A man, a plan, a canal: Panama"
输出：true
输入：s = ""
输出：true
解释：在移除非字母数字字符之后，是一个空字符串，也是回文串。
题目可以很简单，也可以使用高级一些的写法。
如果题目没有给出限制条件，如使用倒转API，String没有提供reverse方法，StringBuilder则提供一个reverse()方法。事实上不使用StringBuilder的reverse()方法，也可以使用String的s.charAt()方法，源码：
public static boolean isPalindrome(String s) {
s = s.toLowerCase();
StringBuilder sb = new StringBuilder();
for (char c: s.toCharArray()) {
if (('a' <= c && c <= 'z') || ('0' <= c && c <= '9')) {
sb.append(c);
}
}
String s1 = sb.toString();
String s2 = sb.reverse().toString();
return s1.equals(s2);
}
题目给出的字符串需要经过去掉【脏】字符处理，故而考虑使用StringBuilder拼接。
如果给出的原始字符串不管是否包括非字母数字字符，则可以考虑定义两个指针（非严格意义上的C语言的指针概念），一个指针从头往中间走，另一个指针从字符串尾部往头走。源码如下：
public static boolean isSymmetrical1(String str) {
boolean flag = true;
// 把字符串转成字符数组，或使用charAt()方法
char[] chs = str.toCharArray();
for (int start = 0, end = chs.length - 1; start <= end; start++, end--) {
if (chs[start] != chs[end]) {
flag = false;
break;
}
}
return flag;
}
回文数
给定整数x ，如果是回文数返回true；否则返回false。例如121是回文，而-123不是。
分析：测试用例（题干）给出的输入包括一个负数，则需考虑前置校验一下。入门题，通过一个while循环取到各个输入的整数的各个位置上的数字，然后使用StringBuilder拼接一下。源码：
public static boolean isPalindrome(int x) {
// 备份原始值
int origin = x;
if (x < 0) {
return false;
}
if (x == 0) {
return true;
}
StringBuilder sb = new StringBuilder();
while (x != 0) {
sb.append(x % 10);
x = x / 10;
}
return String.valueOf(origin).contentEquals(sb);
}
最长回文子串
给定字符串s，找到s中最长的回文子串。比如s = "cdabbacc"，输出abba。
解题方法有很多，如穷举法、动态规划、中心扩展法。
中心扩展法，时间复杂度为O(n^2)，实现相对简单易懂（相对于动态规划算法），适合大多数实际应用。源码如下：
public static String longestPalindrome(String s) {
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private static int expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
public static String longestPalindrome1(String s) {
int ti = 0, maxlen = 0, i, t;
for (i = 0; i < s.length(); i++) {
t = 1;
while (t <= i && i + t < s.length()) {
if (s.charAt(i + t) == s.charAt(i - t)) {
t++;
} else {
break;
}
}
t--;
if (2 * t + 1 > maxlen) {
ti = i - t;
maxlen = 2 * t + 1;
}
}
for (i = 0; i < s.length(); i++) {
t = 1;
while (t <= i + 1 && i + t < s.length()) {
if (s.charAt(i - t + 1) == s.charAt(i + t)) {
t++;
} else {
break;
}
}
t--;
if (2 * t > maxlen) {
ti = i - t + 1;
maxlen = 2 * t;
}
}
return s.substring(ti, ti + maxlen);
}
分割成回文串
给定一个字符串，求其所有可能的分割方案，使得每个子串都是回文串。
困难级别，动态规范解决方法：
public static List<List<String>> partition(String s) {
boolean[][] dp = new boolean[s.length()][s.length()];
for (int len = 1; len <= s.length(); len++) {
for (int i = 0; i <= s.length() - len; i++) {
if (len == 1) {
dp[i][i] = true;
} else if (s.charAt(i) == s.charAt(i + len - 1) && (len == 2 || dp[i + 1][i + len - 2])) {
dp[i][i + len - 1] = true;
}
}
}
return solution(s, 0, dp);
}
private static List<List<String>> solution(String s, int start, boolean[][] dp) {
ArrayList<List<String>> list = new ArrayList<>();
if (start == s.length()) {
List<String> li = new ArrayList<>();
list.add(li);
return list;
}
for (int i = start; i < s.length(); i++) {
if (dp[start][i]) {
String first = s.substring(start, i + 1);
for (List<String> li : solution(s, i + 1, dp)) {
li.add(0, first);
list.add(li);
}
}
}
return list;
}
最短回文串
将给定的字符串补齐为回文串，返回补充字符后的回文串。要求：长度最短 + 只能在前面补字符
public static String shortestPalindrome(String s) {
StringBuilder r = new StringBuilder(s).reverse();
String str = s + "#" + r;
int[] next = next(str);
String prefix = r.substring(0, r.length() - next[str.length()]);
return prefix + s;
}
private static int[] next(String P) {
int[] next = new int[P.length() + 1];
next[0] = -1;
int k = -1;
int i = 1;
while (i < next.length) {
if (k == -1 || P.charAt(k) == P.charAt(i - 1)) {
next[i++] = ++k;
} else {
k = next[k];
}
}
return next;
}
回文链表
判断给定的单链表是否为回文链表。
分析：很多链接问题都可以通过指定两个快慢速度不一致的指针，遍历链表，进行判断。
public static boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
ListNode slow = head;
ListNode quick = head;
while (quick != null && quick.next != null) {
quick = quick.next.next;
slow = slow.next;
}
ListNode pre = null;
ListNode p = slow;
while (p != null) {
ListNode temp = p.next;
p.next = pre;
pre = p;
p = temp;
}
while (pre != null) {
if (pre.val == head.val) {
pre = pre.next;
head = head.next;
} else {
return false;
}
}
return true;
}
链表的定义：
private static class ListNode {
private ListNode next;
private final int val;
ListNode(int val) {
this.val = val;
}
}