-
Notifications
You must be signed in to change notification settings - Fork 0
/
5.cpp
57 lines (52 loc) · 1.21 KB
/
5.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <map>
#include <vector>
#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
string longestPalindrome(string s) {
int length = s.length();
if(length==0||length==1) return s;
int start= 0, end = 0;
int maxLength = 1;
map<char,vector<int> > already;
for(int i=0;i<length;i++){
map<char,vector<int> >::iterator it = already.find(s[i]);
if(it==already.end()){
already[s[i]] = vector<int>(1,i);
}else{
vector<int> v = already[s[i]];
for(int j=0;j<v.size();j++){
if(isPalindrome(s,v[j],i)){
if(i-v[j]+1 >= maxLength){
maxLength = i-v[j] + 1;
start = v[j];
end = i;
}
}
}
v.push_back(i);
already[s[i]] = v;
}
}
return s.substr(start, maxLength);
}
private:
bool isPalindrome(const string &s, int left, int right){
while(left < right){
if(s[left] != s[right]){
return false;
}
left++;
right--;
}
return true;
}
};
int main(){
Solution s;
string r = s.longestPalindrome("bac1234321abc");
cout << r << endl;
return 0;
}