问题描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

示例 1：
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。

示例 2：
输入: “cbbd”
输出: “bb”

维基百科解释
leetcode题目

算法解决

暴力法

使用start指针和end指针，两个for循环内不断找最大回文子串，时间复杂度O(n^2)。

Manacher算法

个人觉得Manacher算法来源于中心拓展法。
一个很直观的想法是，以某个字符为中心拓展，来查找最长子串。但这种方法没有降低时间复杂度，主要存在2个问题：

1. 回文串长度为奇数和偶数时由于对称轴不同要分开考虑；
2. 没有利用已经获取的回文串信息。

针对上面两个问题，Manacher算法解决之道：

1. 插入无关字符，使所有子串长度统一为奇数；
2. 利用回文串信息，实现如下：
   1. 使用数组记录每个字符的回文半径R[i]；
   2. 标记拓展到字符串最右端的回文串的对称中心pos，以及MaxRight；
   3. 当前下标i必定大于pos；
   4. 若pos<i<=maxRight，则找到i关于pos的对称点j，则字符i的回文拓展位置在R[j]的长度上往左右两边拓展；
   5. 若i>maxRight，则i关于pos的对称点不在pos范围内，不存在可使用的回文信息，常规左右拓展；
   6. 不断更新pos和MaxRight;
   7. 注意边界问题。

代码

char* insertChar(char* s) {
	int len = 2 * strlen(s)+2;
	char *s1 = (char*)malloc(len * sizeof(char));
	for (int i = 0; i < len - 1; i++) {
		if (i % 2) {
			s1[i] = s[i / 2];
		}
		else {
			s1[i] = '*';
		}
	}
	s1[len - 1] = '\0';
	return s1;
}
char* deleteChar(char* s) {
	int len = strlen(s) / 2 + 2;
	char *s1 = (char*)malloc(len * sizeof(char));
	for (int i = 0; i < len - 1; i++) {
		s1[i] = s[2 * i+1];
	}
	s1[len - 1] = '\0';
	return s1;
}
char* getString(char* s, int pos, int r) {
	int len = 2 * r;
	char *s1 = (char*)malloc(len * sizeof(char));
	for (int i = 0; i < len - 1; i++) {
		s1[i] = s[pos - r + 1 + i];
	}
	s1[len - 1] = '\0';
	return s1;
}
char* longestPalindrome(char* s) {

	char* s1 = insertChar(s);
	int len = strlen(s1);
	int pos = 0;//标记与Maxright对应的下标
	int * R = (int*)malloc(sizeof(int)*len);
	int maxIndex = 0;//最大回文子串的对称中心
	//初始化R
	for (int i = 0; i < len; i++)  R[i] = 1;

	int i = 0;
	while (s1[i] != '\0') {
		int j = 2 * pos - i;
		if (i - (R[i] - 1) >= 0 && j >= i - (R[i] - 1)) {//j在pos回文段内
			if (i + R[j] - 1 <= pos + R[pos] - 1) {//i+R[j]-1<=MaxRight，不可能越界
				//在R[j]基础上拓展
				R[i] = R[j];
				int right = i + R[i];
				int left = i - R[i];
				while (left >= 0 && right <= len - 1 && s1[left] == s1[right]) {
					R[i]++;
					left--;
					right++;
				}
				//判断pos是否更新
				if (i + R[i] - 1 > pos + R[pos] - 1) {
					pos = i;
				}

			}
			else {//i+R[j]-1超出了MaxRight，有可能越界
				if (i + R[j] - 1 <= len - 1) { //未越界
					//在R[j]基础上拓展
					R[i] = R[j];
					int right = i + R[i];
					int left = i - R[i];
					while (left >= 0 && right <= len - 1 && s1[left] == s1[right]) {
						R[i]++;
						left--;
						right++;
					}
				}
				else {//越界
					R[i] = len - 1 - i + 1;
				}
				pos = i;
			}
		}
		else {//j在pos回文段外
			int right = i + 1;
			int left = i - 1;
			while (left >= 0 && right <= len - 1 && s1[left] == s1[right]) {
				R[i]++;
				left--;
				right++;
			}
			pos = i;
		}
		if (R[i] > R[maxIndex]) {
			maxIndex = i;
		}
		i++;
	}

	char* s2 = getString(s1, maxIndex, R[maxIndex]);
	free(s1);
	char* s3 = deleteChar(s2);
	free(s2);
	return s3;
}

不过不知道为啥在leetcode上面报执行错误，在本地跑通了。

动态规化

简书上看到有人用动态规划写的。动态规划还没学习，不过看了下思路，觉得挺巧妙的。
Manacher算法是从左到右逐次遍历，并且利用已有回文信息来初始化新子串边界；动态规划思路类似递归：

1. (i，j)为回文=（i+1，j-1)为回文&&i元素==j元素；
2. (i+1，j-1)比(i，j)规模小，因此在之前被计算了；

代码

class Solution {
   public String longestPalindrome(String s) {
        if (s.isEmpty()) {
            return s;
        }
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int left = 0;
        int right = 0;
        for (int i = n - 2; i >= 0; i--) {
            dp[i][i] = true;
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = s.charAt(i) == s.charAt(j) &&( j-i<3||dp[i+1][j-1]);//小于3是因为aba一定是回文
                if(dp[i][j]&&right-left<j-i){
                    left=i;
                    right=j;
                }
            }
        }
        return s.substring(left,right+1);
    }
}