leetcode05最长回文子串

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

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

看到一道题没什么思路，首推暴力法，无脑暴力，写出来再说

• 暴力法，找出每一个子串，并判断是否为回文字符串，注意边界问题
• 定义一个数组记录找到的最长回文字符串的左右边界
• 暴力法的时间复杂度为O(n^3),空间复杂度O(1)

public String longestPalindrome(String s) {
		int[] bound = new int[2];
		int n = s.length(), res = 0;
		for (int i = 0; i != n; i++) {
			for (int j = 0; j != n; j++) {
				// 判断此子串是否为回文子串
				boolean f = ifPalindrome(s, i, j);
				if (f && (j - i + 1) > res) {
					res = j - i + 1;
					bound[0] = i;
					bound[1] = j + 1;
				}
			}
		}
		return s.substring(bound[0], bound[1]);

中心法，遍历字符串，把每个字符当做中心，根据条件往两边扩，记录最大值 奇数数组好扩 “aba” 偶数数组不好扩 “abba”，找不到中心，所以要变形

• "#a#b#b#a#"这样的话中心是第三个# 只记左边长度是4，等价总长 看
• 一下扩展奇数数组"aba", “#a#b#a#”，b为中心，左边长度是3
• 变形需要用到StringBuilder吧？
• 中心法时间复杂度O(n^2) 空间复杂度O(n)

public String longestPalindrome_1(String s) {
		if (s == null || s.length() < 2)
			return s;
		int n = s.length(), res = 0;
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i != s.length(); i++) {
			sb.append("#" + s.charAt(i));
		}
		sb.append("#");
		int index = 0;
		s = sb.toString();// 变形后
		for (int i = 0; i != s.length(); i++) {
			// 这里判断能不能往外扩的最长串,返回值要
			int len = caculateLong(s, i);
			// 更新
			if (len > res) {
				res = len;
				index = i;
			}
		}
		/*
		 * substring(a,b); 截取字符串上的距离，左闭右开 [a,b) replace(rex,"要替换的值"); 替换字符串中某些字符
		 */
		return s.substring(index - res, index + res + 1).replace("#", "");
	}
	



public int caculateLong(String s, int i) {// 时间复杂度 O(n)
		int n = s.length(), l = i - 1, r = i + 1, res = 0;
		while (l >= 0 && r < n) {// 最大可以扩到[0,n-1]
			if (s.charAt(l--) == s.charAt(r++)) {
				res++;
			} else
				break;
		}
		return res;
	}

回文中心新解，不用对s进行操作，遍历到i时，考虑i是回文中心（奇数） [i,i+1]的中心为回文中心分别考虑这两种情况，得到各自的回文长度，两者中较大的则是当前i位置能求得的最大回文长度

• 奇数 “aba”，有回文中心b ,偶数 “abba” 没有回文中心 奇数：把[i,i]传进函数 特殊处理偶数，把[i,i+1]传进判断函数里
• 1.若s[i]==s[i+1]，则进入2，否则退出判断
• 2.若s[i-1]==s[i+2]，则进入3，
• …
• 最大判断至 s[0] == s[n-1] (整个字符串都为回文字符串)， 最后返回当前回文中心回文字符串的长度：r-l-1

无需扩展

public String longestPalindrome_2(String s) {
		if (s == null || s.length() < 1) {
		return "";
	}
	int e = 0;
	int start = 0;
	for (int i = 0; i != s.length(); i++) {
		// 1.考虑i为回文中心
		int len1 = longPalindrom(s, i, i);
		// 2.考虑[i,i+1]之间为回文中心
		int len2 = longPalindrom(s, i, i + 1);
		int len = Math.max(len1, len2); // 最小回文子串也是其自身 1
		if (len > e - start) {// 这里也要抠，本来[e,s]的长度为s-e+1,既然len>e-s,则len最小也等于s-e+1,可以更新一波
			start = i - (len - 1) / 2;// 举例："aba",b为回文中心，len = 3 , start = 1 - (3-1)/2=0,
			e = i + len / 2;// i/2==(i+1)/2,这里长度是奇数和偶数不影响 end = 1 + 3/2 =2
		}
	}
	return s.substring(start, e + 1);
}

动态规划时间复杂度为O(N2)，空间复杂度为O(N^2），

• 动态规划解法 举例：s=“xabcbay”，其子串"abcba"是回文子串，若x==y，则该串为回文子串
• dp[i][j]:表示字符串[i,j]是否为回文字符串
• 动态递推式：dp[i][j] = dp[i+1][j-1] && s[i]==s[j]
• …
• 最大判断至 s[0] == s[n-1] (整个字符串都为回文字符串)， 最后返回当前回文中心回文字符串的长度：r-l-1

public String longestPalindrome_3(String s) {

		// 先填二维数组能填的部分，第一行dp[0][j]
		if (s == null || s.length() < 1)
			return "";
		int n = s.length();
		boolean[][] dp = new boolean[n][n];// 默认复制为false
		int res = 1, start = 0, end = 0;
		// 初始化，任意一个字符i，[i,i]是回文子串， 如果s[i]==s[i+1]，则[i,i+1]是回文子串
		for (int i = 0; i != n; i++) {
			for (int j = i; j != n; j++) {
				if (i == j) {
					dp[i][j] = true;
				}
				if ((i + 1) != n && s.charAt(i) == s.charAt(i + 1)) {
					dp[i][i + 1] = true;
				}
			}
		}
		// 数组要从下往上填，因为dp[i][j] 根据 dp[i+1][j-1]来推
		for (int i = n - 2; i >= 0; i--) {
			for (int j = 0; j < n; j++) {
				if (i < n - 1 && j >= 1) {
					if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
						dp[i][j] = true;
					}
				}
			}
		}
		for (int k = 0; k != n; k++) {
			for (int j = n - 1; j >= k; j--) {
				if (dp[k][j] && res < (j - k + 1)) {
					res = j - k + 1;
					start = k;
					end = j;
				}
			}
		}
		return s.substring(start, end + 1);
	}

总结：对于数组或者字符串求子串的问题，注意不是子序列，这类题可以使用暴力法找到所有的子串，逐一比较，求得解，当然这种解法是不能通过oj的，复杂度太高。可以往动态规划或者滑动窗口上面想。