Longest Palindromic Substring(C++)
1081 ワード
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Example 2:
class Solution { public: string longestPalindrome(string s) { int n=s.size(); if(n==0) return ""; string lon=s.substr(0,1); for(int i=0;i { string s1=expand(s,i,i); if(lon.size() lon=s1; string s2=expand(s,i,i+1); if(lon.size() lon=s2; } return lon; } string expand(string s,int i,int j) { int l=i,r=j,n=s.size(); while(l>=0&&r<=n-1&&s[l]==s[r]) { l--; r++; } return s.substr(l+1,r-l-1); } };
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
class Solution { public: string longestPalindrome(string s) { int n=s.size(); if(n==0) return ""; string lon=s.substr(0,1); for(int i=0;i { string s1=expand(s,i,i); if(lon.size() lon=s1; string s2=expand(s,i,i+1); if(lon.size() lon=s2; } return lon; } string expand(string s,int i,int j) { int l=i,r=j,n=s.size(); while(l>=0&&r<=n-1&&s[l]==s[r]) { l--; r++; } return s.substr(l+1,r-l-1); } };