β

Longest Palindromic Substring

Michael's Blog 44 阅读

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.

Example:

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

Example:

Input: "cbbd"
Output: "bb"  
public class Solution {  
    public String longestPalindrome(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }
        String result = s.substring(0, 1);
        for (int i = 0; i < s.length(); i++) {
            String str = findLongestPalindrome(s, i, i);
            if (str.length() > result.length()) {
                result = str;
            }
            str = findLongestPalindrome(s, i, i + 1);
            if (str.length() > result.length()) {
                result = str;
            }
        }
        return result;
    }
    String findLongestPalindrome(String s, int start, int end) {
        while (start >= 0 && end <= s.length() - 1 
                && s.charAt(start) == s.charAt(end)) {
            start--;
            end++;
        }
        return s.substring(start + 1, end);
    }
}

Hope this helps,
Michael

作者:Michael's Blog
Thoughts, stories and ideas.
原文地址:Longest Palindromic Substring, 感谢原作者分享。

发表评论