首页 > 其他 > 详细

LeetCode(3)题解: Longest Palindromic Substring

时间:2015-07-25 22:43:43      阅读:237      评论:0      收藏:0      [点我收藏+]

https://leetcode.com/problems/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.

 

思路:

我的思路是遍历字符串,对每个元素用扩张法,找到以这个位置作为回文序列中心左边第一个点的回文序列,因为牵扯到奇偶性,需要遍历两遍。复杂度是O(n^2),但是一般情况这样剪枝比较快。

 

AC代码:  60ms C++

 1 class Solution {
 2 public:
 3     string longestPalindrome(string s) {
 4         int loc,j,l=0,n=s.size();
 5         if (n==0)
 6             return "";
 7         if (n==1)
 8             return s;
 9         for (int i=0;i<n;i++){
10             for(j=0; i-j>=0 && i+j+1<n;j++){
11                 if(s[i-j]!=s[i+j+1])
12                     break;
13             }
14             if(2*j>l){
15                 l=2*j;
16                 loc=i;
17             }
18         }
19         for (int i=0;i<n;i++){
20             
21             for(j=0; i-j>=0 && i+j+2<n;j++){
22                 if(s[i-j]!=s[i+j+2])
23                     break;
24             }
25             if(2*j+1>l){
26                 l=2*j+1;
27                 loc=i;
28             }
29         }
30         return s.substr(loc-l/2+1,l);
31     }
32 };

 

LeetCode(3)题解: Longest Palindromic Substring

原文:http://www.cnblogs.com/aezero/p/4676722.html

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