#LeetCode:5. Longest Palindromic Substring

找出最長迴文子字串。可以將每個字當作是中央去往外擴張,擴張有兩種方式:一種是長度為奇數、另外一種是長度是偶數的狀況,最後找出從哪個字擴張可以得到最大的長度即是答案。

參考做法:LeetCode Solution

C++(8ms)

/*******************************************************/
/* LeetCode 5. Longest Palindromic Substring           */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2018/09/25                                 */
/*******************************************************/
#include <cstdlib>

class Solution {
public:
  string longestPalindrome(string s) {
      if( s.length() < 1 ) return "";

      int start = 0, length = 1;
      for(int i = 0 ; i < s.length() ; ++i){
        int oddStringLength = findPalindromeFromCenter(s, i, i);
        int evenStringLength = findPalindromeFromCenter(s, i, i+1);
        int maxLength = max(oddStringLength, evenStringLength);
        if(maxLength > length){
          length = maxLength;
          start = i - (maxLength - 1) / 2;
        }
      }

      return s.substr(start, length);
  }

  int findPalindromeFromCenter(const string& s, int left, int right){
    while(left >= 0 && right < s.length() && s[left] == s[right]) --left, ++right;
    return right - left - 1;
  }
};
廣告

Comment

There is no comment on this post. Be the first one.

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料

%d 位部落客按了讚: