首页 > 其他 > 详细

lintcode-medium-Longest Palindromic Substring

时间:2016-03-29 14:16:28      阅读:229      评论:0      收藏:0      [点我收藏+]

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.

 

Example

Given the string = "abcdzdcab", return "cdzdc".

Challenge

O(n2) time is acceptable. Can you do it in O(n) time.

 

n^2做法:

public class Solution {
    /**
     * @param s input string
     * @return the longest palindromic substring
     */
    public String longestPalindrome(String s) {
        // Write your code here
        if(s == null || s.length() == 0)
            return s;
        
        String result = s.substring(0, 1);
        
        for(int i = 1; i < s.length(); i++){
            int left = i;
            int right = i;
            
            while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
                left--;
                right++;
            }
            
            String temp = s.substring(left + 1, right);
            if(temp.length() > result.length())
                result = temp;
        }
        
        for(int i = 0; i < s.length(); i++){
            int left = i;
            int right = i + 1;
            
            while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
                left--;
                right++;
            }
            
            String temp = s.substring(left + 1, right);
            if(temp.length() > result.length())
                result = temp;
        }
        
        return result;
    }
}

 

lintcode-medium-Longest Palindromic Substring

原文:http://www.cnblogs.com/goblinengineer/p/5332514.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!