2015年5月27日星期三

Longest Palindromic Substring leetcode

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.
这道题可以以串心为中心 往字符串两边扫 找到最长的回文串
对于每个子串的中心(可以是一个字符,或者是两个字符的间隙,比如串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)。”引自http://codeganker.blogspot.com/2014/02/longest-palindromic-substring-leetcode.html)
public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            String tem = helper(s, i, i);
            if (tem.length() > res.length()) {
                res = tem;
            }
            tem = helper(s, i, i + 1);
            if (tem.length() > res.length()) {
                res = tem;
            }
        }
        return res;
    }
    public String helper(String s, int start, int end) {
        while (start>= 0 && end < s.length() ) {
            if (s.charAt(start) == s.charAt(end)) {
                start--;
                end++;
            } else {
                break;
            }
        }
        return s.substring(start + 1, end);//此时start位和end位的不相等
    }
}

没有评论:

发表评论