[Java]LeetCode5 Longest Palindromic Substring

Given a stringS, find the longest palindromic substring inS. You may assume that the maximum length ofSis 1000, and there exists one unique longest palindromic substring.

题意：求字符串中最长的回文

感觉这题不难，可以这样想，设置两个指针，分别对应0，len-1。

比如从第一个字符开始，abababac，我们可以找a出现的位置，然后以第一个a与每个a作为一段。判断每一段是否是回文，，因为是从后往前查找的，所以第一个找到的肯定是这一次查找中最长的回文，然后一次第2个字符，第3个字符。这个想法在字符串中的字符不一样的时候比较好。但是如果字符中出现的例如aaaaaabcaaaaa这样的话，就不佳了。在leetcode中一测试,果然TimeLimited。

第二个想法，算是逆推法，既然求的是回文，回文的字符是对称的。我们可以先确定回文的中心，回文的中心，奇数的时候是一个，偶数的时候是两个。分别向中心的两边进行匹配，判断是否相等，从而计算回文的长度。

代码如下：

public static String longestPalindrome(String s) {if(s.isEmpty()||s.length()==1)return s;String longest=s.substring(0,1);for(int i=0;i<s.length();i++){//将i作为中心,获取最长的字符串String tmp=isPalindrome(s,i,i);if(tmp.length()>longest.length())longest=tmp;//将i,i+1作为中心，获得最长的字符串tmp=isPalindrome(s,i,i+1);if(tmp.length()>longest.length())longest=tmp;}return longest;}private static String isPalindrome(String s, int start, int end)    {        // TODO Auto-generated method stub        while(start>=0&&end<=s.length()-1&&s.charAt(start)==s.charAt(end))        {            start–;            end++;        }        return s.substring(start+1,end);    }

去陌生的街角，去做一切我们曾经或现在也很想做的事情，