[leetcode] Longest Palindromic Substring

题目：（String）

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

 

题解：自己先写了一个循环所有substring的，超时。

public class Solution {
    public String longestPalindrome(String s) {
        if(s.length()==0||s.length()==1||checkIsPalindrome(s))
           return s;
        
        int len = s.length();
        
        for(int i =len-1 ; i>=1 ;i--)
        {
            for(int j =0; j<=len-i; j++)
            {
                if(checkIsPalindrome(s.substring(j,j+i)))
                  return s.substring(j,j+i);
            }
        }
        
        return s;
    }
    
    public boolean checkIsPalindrome(String s)
    {
        Stack<Character> stack = new Stack<Character>();
        int len =s.length();
        if(len%2==0)
        {
            for(int i=0;i<len/2;i++)
            {
                stack.push(s.charAt(i));
            }
            
            for(int i=len/2;i<len;i++)
            {
                char temp = stack.pop();
                if(temp!=s.charAt(i))
                   return false;
            }
            return true;
        }
        else
        {
            for(int i=0;i<len/2;i++)
            {
                stack.push(s.charAt(i));
            }
            
            for(int i=len/2+1;i<len;i++)
            {
                char temp = stack.pop();
                if(temp!=s.charAt(i))
                   return false;
            }
            return true;
        }
    }
}

看了别人的方法：

第二种方法“是对于每个子串的中心（可以是一个字符，或者是两个字符的间隙，比如串abc,中心可以是a,b,c,或者是ab的间隙，bc的间隙，例如aba是回文，abba也是回文，这两种情况要分情况考虑）往两边同时进 行扫描，直到不是回文串为止。假设字符串的长度为n,那么中心的个数为2*n-1(字符作为中心有n个，间隙有n-1个）。对于每个中心往两边扫描的复杂 度为O(n),所以时间复杂度为O((2*n-1)*n)=O(n^2),空间复杂度为O(1)。”引自Code ganker（http://codeganker.blogspot.com/2014/02/longest-palindromic-substring-leetcode.html）

public class Solution {
    public String longestPalindrome(String s) {
        if(s.length()==0||s.length()==1)
           return s;
          
        String longest = s.substring(0,1);
        for(int i=0;i<s.length(); i++)
        {
            String temp = buildTheLargeSubstring(s,i,i);
            
            if(temp.length()>longest.length())
               longest =temp;
               
            temp = buildTheLargeSubstring(s,i,i+1);
            
            if(temp.length()>longest.length())
               longest =temp;
        }
        
        return longest;
    }
    
    public String buildTheLargeSubstring(String s, int begin, int end)
    {
        while(begin>=0&&end<=s.length()-1&&s.charAt(begin)==s.charAt(end))
        {
            begin--;
            end++;
        }
        
        return s.substring(begin+1,end);
    }
}