LeetCode(Array&String)Longest Palindromic Substring

2018-06-21

Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

1
2
3

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

1 2	Input: "cbbd" Output: "bb"

思路：想到了定义一个辅助函数来判断输入字符串是不是回文串，然后在输入字符串中循环遍历找到头尾相同的字符串选中调用辅助函数进行判断，如果子串是回文串就将该串记录下来，以后得到的每个子串和之前记录的最大的子串长度max进行比较，如果有大于max的子串，将max子串更新为该子串，最后返回max子串即可。

代码如下：最后超时了。还需优化

class Solution {
    public String longestPalindrome(String s) {
        int len=s.length();
        if(len==0){
            return null;
        }
        if(len==1){
            return s;
        }
        int max=0;
        String res="";
        for(int i=0;i<len;i++){
            char sr=s.charAt(i);
            for(int j=i+1;j<len;j++){
                if(sr==s.charAt(j)){
                    String temp=new String(s.substring(i,j+1));
                    if(isPalindrome(temp)){
                        if(max<temp.length()){
                            max=temp.length();
                            res=temp;
                        }
                    }
                }
            }
        }
        if(len>1 && res==""){
            return ""+s.charAt(0);
        }
        return res;
    }
    public boolean isPalindrome(String s){
        int len=s.length();
        int i=0;
        while(i<len/2){
            if(s.charAt(i)!=s.charAt(len-1-i)){
                break;
            }
            i++;
        }
        if(i==len/2){
            return true;
        }else{
            return false;
        }
    }
}

对上述代码做优化：发现可以优化的地方是对子字符串做是否是回文的判断时，可以不用每一次都做截取操作，只截取判断后是回文的子字符串，这样可以减少很多的截取操作，但是相应的也要更改判断回文的函数。具体代码如下：优化后的代码通过了所有的测试用例。

class Solution {
    public String longestPalindrome(String s) {
            int len=s.length();
	        if(len==0){
	            return null;
	        }
	        if(len==1){
	            return s;
	        }
	        int max=0;
	        String res="";
	        for(int i=0;i<len;i++){
	            char sr=s.charAt(i);
	            for(int j=i+1;j<len;j++){
	                if(sr==s.charAt(j)){
                        //优化了判别函数以及截取子字符串的时机
	                    if(isPalindrome(s,i,j)){
	                        if(max<j-i+1){
	                            max=j-i+1;
	                            res=s.substring(i, j+1);
	                        }
	                    }
	                }
	            }
	        }
	        if(len>1 && res==""){
	            return ""+s.charAt(0);
	        }
	        return res;
    }
    //优化后的判别函数
  	public boolean isPalindrome(String s ,int start,int end){
	        int len=end-start+1;
	        if(start>end){
	            return false;
	        }
	        int i=start;
	        int k=end;
	        while(i<start+len/2 && s.charAt(i)==s.charAt(k)){
	            i++;
	            k--;
	        }
	        if(i==start+len/2){
	            return true;
	        }else{
	            return false;
	        }
    }
}