5、最长回文子串(动态规划）

解题过程中我的思路，不喜勿喷，欢迎留言讨论。

暴力解法我的思路：枚举所给字符串的所有子串(用一个二重循环即可)，再用一个循环来判断枚举出来的子串是否为回文串。判断的方法为将子串的头和尾字符进行比较，看他们是否相等，若相等则头尾同时向中心移动一个字符继续比较，直到这样所有成对的字符都相等或者有一对不相等的时候就退出该层循环。代码如下：

暴力解法：

class Solution {
    public String longestPalindrome(String s) {
        String longer = "";
        String longest = "";
        for ( int j=0; j<s.length(); j++){
            for ( int k=j+1; k<s.length()+1; k++){
                longer = s.substring(j,k);
                if ( longer.length() >= longest.length() ) {
                	boolean ishw = true;
                    for (  int i=0; i<(longer.length()/2); i++ ){
                        if ( !(longer.substring(i,i+1)).equals(longer.substring(longer.length()-1-i, longer.length()-i)) ){
                            ishw = false;
                            break;
                        }
                    }
                    if ( ishw ){
                    	longest = longer;
                    }
                } 
            }
        }
        return longest; 
    }
}
           

上面的暴力解法虽然没问题，但是运行时间超出限制，该暴力解法暴力的还不够好，还有一个更好一点的暴力解法(只记录子串的长度和起始位置，没有必要截取，这是因为截取字符串也要消耗性能。这样也不需要使用equals来判断字符是否相等)，他主要是一开始将所给字符串转换成字符数组，在判断头尾两字符是否相等时用的是简单运算符 " != "，而我的暴力解法判断头尾两字符用的是equals。更好一点的暴力解法代码如下：

public class Solution {

    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        // s.charAt(i) 每次都会检查数组下标越界，因此先转换成字符数组
        char[] charArray = s.toCharArray();

        // 枚举所有长度大于 1 的子串 charArray[i..j]
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                if (j - i + 1 > maxLen && validPalindromic(charArray, i, j)) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }

    /**
     * 验证子串 s[left..right] 是否为回文串
     */
    private boolean validPalindromic(char[] charArray, int left, int right) {
        while (left < right) {
            if (charArray[left] != charArray[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
           

暴力解法时间复杂度高，编写简单。由于编写正确性的可能性很大，可以使用暴力匹配算法检验我们编写的其它算法是否正确。优化的解法在很多时候，是基于“暴力解法”，以空间换时间得到的，因此思考清楚暴力解法，分析其缺点，很多时候能为我们打开思路。

动态规划解法：1、在两头字符相等的情况下，整体是否为回文由中间这部分是否为回文决定。所以将状态定义为：一个子串是否为回文，dp[i][j]表示子串s[i...j]是否为回文子串。得到状态转移方程：dp[i][j]=(s[i]==s[j]) and dp[i+1][j-1]。边界条件：(j-1)-(i+1)+1<2，即j-i<3，表示中间的子串长度是0或1，所以中间子串肯定是回文。

2、动态规划要做的就是填表，将二维数组填完，基本上就得到了最终结果。

3、填表时需要注意的事项：①使用 i j 序号来表示一个字符串，i为字符串上界，j为字符串下界，不需要真正的截取字符串(类似暴力解法2)；②假设表格横向是 j ，纵向是i ，由于 i < j 所以填表只是在填写表的上半部分，并且由于状态转移之后，参考的是dp[i+1][j-1] 的状态，i+1在 i 的下面一行，j-1在 j 的左边一列，因此我们需要从左到右一列一列的更新表格，这样才能用到我们之前更新的结果；③在一个字符串更新完成之后就可以开始判断字符串是否为回文，即填表与回文最长回文判断同时进行(在一个循环嵌套里但上下顺序不同)。

代码如下：

public class Solution5{
	public static String longestPalindrome(String s) {
		int len = s.length();
		if (len<2) {
			return s;
		}
		int maxLen = 1;
		int begin = 0;

		char[] charArray = s.toCharArray();

		boolean[][] dp = new boolean[len][len];
		for (int i=0; i<len; i++){
            dp[i][i] = true;
		}

		for (int j=1; j<len; j++) {
		    for (int i=0; i<j; i++) {
			    if (charArray[i]==charArray[j]) {//头尾字符相等
				    if (j-i<3) {//头尾去掉剩下字符数量为0或1,不构成子串(边界问题)
						dp[i][j] = true;
					}else {
						dp[i][j] = dp[i+1][j-1];
					}
				}else {//头尾字符不等
					dp[i][j] = false;
				}
                
                if (dp[i][j] && j-i+1 > maxLen ) {
					maxLen = j-1+1;
					begin = i;
				}
			}
		}
		return s.substring(begin, begin+maxLen);
	}
}
           

总结一下：遇到字符串中字符的比较，最好将字符串转换成字符数组，用两个变量记录字符串头和尾就可以表示一个字符串。(不然就像我原始的想法暴力解法1一样，非常不灵活，这样也就没有后面的优化部分)

               初遇动态规划，理解一下状态转移方程就行(头尾字符相等的情况下，字符串是否为回文由去掉头尾的字符串是否为回文决定，所以状态就为：字符串是否为回文。按照这个思路填写状态表即可，空间换时间。），后面在遇到动态规划方法要熟练掌握。