5. 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, and there exists one unique longest palindromic substring.

思路:参考某位大神的解题思路,找到最长的palindromic子串,找palindrome的时候可以从某个点坐标i 按照偶数展开(i-1, i+1), 或者按照奇数展开(i,i+1)。 找palindrome的方法可以两个指针挨个比较。因为需要找最长的palindrome子串,可以用一个全局的maxLen变量每次找到子串后进行比较,并把较长的那个赋给最后结果。

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) return "";
        String maxRes = ""; 
        int maxLen = 0;
        // even expand
        for (int i = 0; i < s.length(); i++) {
            String tmp = expand(s, i - 1, i + 1);
            if (maxLen < tmp.length()) {
                maxLen = tmp.length();
                maxRes = tmp;
            }

        }
        // odd expand
        for (int i = 0; i < s.length(); i++) {
            String tmp = expand(s, i, i + 1);
            if (maxLen < tmp.length()) {
                maxLen = tmp.length();
                maxRes = tmp;
            }

        }
        return maxRes;
    }

    public String expand(String s, int left, int right) {
        while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return s.substring(left + 1, right);
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s