2021. 3. 20. 16:17ㆍ알고리즘/LeetCode
1. Problem
Given s string and find longest palindromic substring
2. base: len
find palindromic based len: s.size() ~ 1
bottom-up:
iteration start => 1 -> s.size()
You have to do unnecessary nested calculation. and must use dp algorithm.
top-down: i
teration start => s.size() -> 1
If find palindromic, immediately return substring.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
bool isPalindromic(string::iterator first, string::iterator last) {
while(first != last && (first != --last)) {
if(*(first++) != *last) return false;
}
return true;
}
string longestPalindrome(string s) {
for(int len = s.size(); len >= 1; len--) {
for(int i = 0; i + len <= s.size(); i++)
if(isPalindromic(s.begin() + i, s.begin() + i + len))
return s.substr(i, len);
}
return s.substr(0, 1);
}
};
|
cs |
3. base: center
Palindromic : left - center - right
and left == right
find all palindromic and return max len substring
Accepted 4ms c++ solution. - LeetCode Discuss
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public:
std::string longestPalindrome(std::string s) {
if (s.size() < 2)
return s;
int len = s.size(), max_left = 0, max_len = 1, left, right;
for (int start = 0; start < len && len - start > max_len / 2;) {
left = right = start;
while (right < len - 1 && s[right + 1] == s[right])
++right;
start = right + 1;
while (right < len - 1 && left > 0 && s[right + 1] == s[left - 1]) {
++right;
--left;
}
if (max_len < right - left + 1) {
max_left = left;
max_len = right - left + 1;
}
}
return s.substr(max_left, max_len);
}
};
|
cs |
4. Manacher's Algorithm
it is O(n) algorithm.
and based on center.
left - center - right
algospot.com :: Manacher's algorithm
this is only use 'odd palindromic'.
and if you want 'even', revise string to => s[0] + '#' + s[1] + '#' ....
2*p -1 == i'
p == maximum r.. -> use: i is conclude r? => erase nested calc
r = p + d[p]
5: if (i <= r) d[i] = min(d[2*p-i], r-i);
====> if conclude
========> if have i' palindromic and conclude in r => can use it
========> but if it is bigger than r => cant' use it and use r-i
==> if have not i'palindromic => d[i] = 1
=>This tells you why you should use 'min' function
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
vector<int> manachers(string str){
int N = str.size(), r = 0, p = 0;
vector<int> d(N, 0);
for (int i = 0; i < N; i++){
if (i <= r) d[i] = min(d[2*p-i], r-i);
while (i - d[i] - 1 >= 0 && i + d[i] + 1 < N
&& str[i - d[i] - 1] == str[i + d[i] +1 ]) d[i]++;
if (r < i + d[i]) {
r = i + d[i];
p = i;
}
}
return d;
}
|
cs |
'알고리즘 > LeetCode' 카테고리의 다른 글
[LeetCode] [C++] Reverse Integer (0) | 2021.05.11 |
---|---|
[LeetCode] [Medium] ZigZag Conversion (0) | 2021.03.21 |
[LeetCode] [Medium] Longest Substring Without Repeating Characters (0) | 2021.03.18 |
[LeetCode] [Medium] Add Two Numbers (linked list) (0) | 2021.03.17 |
[LeetCode] [easy] Two Sum (brute-force, map) (0) | 2021.03.16 |