leetcode 5最长回文子串 (leetcode一周目结束)

不知不觉就刷完了五十道leetcode算法题，这么算起来整个大一也差不多刷了120题左右的样子。虽然大一上很遗憾没有继续坚持打ACM，但是同样也有了很多学习其他除了算法外的知识的时间，不过刷题确实可以改变代码习惯和提高编程水平，这也是我坚持学习算法的原因。这一周目的刷题就到此为止了，我的大一的算法+开发并行的学习方式让我的代码水平有了很大的提高。大二开始我应该就开始专注学习Java开发了。啊，大一过的好充实啊！(然后就开始疯狂预习期末考555)。

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

示例 1：

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

输入: "cbbd"
输出: "bb"

题解

这题我是用的中心拓展法，其实一开始我根本不知道这个方法叫中心拓展法，写出来后看了题解才知道这个居然有名字。思路就是字符串的每一位其实都是一个回文子串的中心，只要从中心向外拓展就可以达到检查回文子串的目的。在这个过程中需要维护两个指向回文子串头和尾的指针，代码如下

class Solution {
    public String longestPalindrome(String s) {
        int maxNum = 1, temp = 1, i,j;
        // s为空情况
        if (s.length() == 0) {
            return "";
        }
        // 设置初始值
        String ansString = s.substring(0,1);
        for (i=0; i<s.length(); i++) {
            // 按奇数长度拓展
            for (j=0; (i-j) > 0 && (i+j+1) < s.length(); j++) {
                if(s.charAt(i-j-1) != s.charAt(i+j+1)) {
                    break;
                }    
                // 记录此循环回文长度
                temp = (j+1)*2+1;
            }
            if (temp > maxNum) {
                maxNum = temp;
                ansString = s.substring(i-j, i-j+maxNum);
            }
            // 按偶数长度拓展
            for (j = 0; (i-j) >= 0 && (i+j+1) < s.length(); j++) {
                if(s.charAt(i-j) != s.charAt(i+j+1)) {
                    break;
                }           
                temp = j*2+2;                
            }
            if (temp > maxNum) {
                // 推导得j需要减一
                j-=1;
                maxNum = temp;
                ansString = s.substring(i-j, i-j+maxNum);  
            }
        }
        return ansString.toString();
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        String ansString = s.longestPalindrome("cccc");
        System.out.println(ansString);
    }
}