LeetCode(3)题解: Longest Palindromic Substring

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++

 class Solution {

 public:

     string longestPalindrome(string s) {

         int loc,j,l=,n=s.size();

         if (n==)

             return "";

         if (n==)

             return s;

         for (int i=;i<n;i++){

             for(j=; i-j>= && i+j+<n;j++){

                 if(s[i-j]!=s[i+j+])

                     break;

             }

             if(*j>l){

                 l=*j;

                 loc=i;

             }

         }

         for (int i=;i<n;i++){

             for(j=; i-j>= && i+j+<n;j++){

                 if(s[i-j]!=s[i+j+])

                     break;

             }

             if(*j+>l){

                 l=*j+;

                 loc=i;

             }

         }

         return s.substr(loc-l/+,l);

     }

 };

巴特西

LeetCode(3)题解: Longest Palindromic Substring

最新文章

热门文章