5. Longest Palindromic Substring

2019-11-06 07:24:27

字体：大中小

来源：转载

供稿：网友

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.Example:Input: "babad"Output: "bab"Note: "aba" is also a valid answer.Example:Input: "cbbd"Output: "bb"

今天先上一种解法，递归：

class Solution {public: string longestPalindrome(string s) { if(s.empty()) return 0; int start_pos = 0, max_len = 1; //start_pos default 0 because max_len default 1 const int len = s.length(); for(int i=0; i<len-1; ++i){ extend_palindrome(s, len, i, i, start_pos, max_len); //assume odd length, try to extend palindrome as possible extend_palindrome(s, len, i, i+1, start_pos, max_len); //assume even length } return s.substr(start_pos, max_len); } void extend_palindrome(string& s, int len, int left, int right, int& start_pos, int& max_len){ while(left >= 0 && right < len && s[left] == s[right]){ --left; ++right; } if(max_len < right-left-1){ start_pos = left + 1; max_len = right - left - 1; } }};

为什么要有两种情况呢：比如abba和abab分别就是和偶数个最长和奇数个最长的情况。

上一篇：Windows API概述

下一篇：【剑指offer】面试题16：反转链表