LeetCode-LongestPalindromicSubstring

12/12/2015来源:Java教程人气:1236

题目:

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.

思路:

以每个点为基础,寻找回文字符串,两种情况,一种是形如aba,中心店两边是对称的,长度为奇数,另一种是形如aa,长度为偶数。

package string;

public class LongestPalindromicSubstring {

    public String longestPalindrome(String s) {
        int len = s.length();
        String max = "";
        for (int i = 0; i < len; ++i) {
            String res = getStr(s, len, i, i);
            if (res.length() > max.length())
                max = res;
            if (i + 1 < len && s.charAt(i) == s.charAt(i + 1)) {
                res = getStr(s, len, i, i + 1);
                if (res.length() > max.length())
                    max = res;
            }
        }
        
        return max;
    }
    
    PRivate String getStr(String s, int len, int left, int right) {
        while (right < len && left >= 0 && s.charAt(left) == s.charAt(right)) {
            --left;
            ++right;
        }
        return s.substring(left + 1, right);
    }
        
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        LongestPalindromicSubstring l = new LongestPalindromicSubstring();
        System.out.println(l.longestPalindrome("aabbcc"));
    }

}