Yesterday is a palindrome day! 22022022!
And I remembered I talked about a palindromic sub-string problem on Leetcode in this post. I used Manacher's Algorithm to solve it. It's efficient but really hard to get it right in one go. Especially for me :(
The easy way
So I've got a much easier version here - yet not super efficient. But it's really easier, to understand and to write. I got it right at the first try.
The idea is, from each character in the string, using two indexes (pointers) going left and right to check both characters, until they are different. For instance for the string
"a b c d e f e d g h i"
The blue arrow indicates that we go through each character of the string, and the red arrows indicate two pointers, starting from each character, going one step each time to left and right, checking if the current characters are the same or not. If same, then we are having a palindromic string at the moment, so we can go check the next left and right characters.
We also need to think about the case of even characters:
We can write a function to return the palindromic sub-string, given the whole string and the character index (the blue arrow pointing to) as the parameters:
string palindrome(string& s, int l, int r) {
while (l >= 0 && r < s.size() && s[l] == s[r]) {
l--;
r++;
}
return s.substr(l + 1, r - l - 1);
}
For a string with odd number of characters, call the function with l = r; otherwise for an "even string", call it with r = l + 1
The solution is as below. 42 ms, 22.7 MB.
class Solution {
public:
string longestPalindrome(string s) {
string oddStr, evenStr;
string ret = "";
// Go through each character of the string
for (int i = 0; i < s.size(); i++) {
// As mentioned, we need to think about both odd and even characters
oddStr = palindrome(s, i, i);
evenStr = palindrome(s, i, i + 1);
// Check if the current palindrome is the longest
// If yes, update ret
if (oddStr.size() > evenStr.size()){
if (oddStr.size() > ret.size()) {
ret = oddStr;
}
} else {
if (evenStr.size() > ret.size()) {
ret = evenStr;
}
}
}
return ret;
}
string palindrome(string& s, int l, int r) {
// If the characters the left and right pointers are pointing to are the same
// Then we currently have a palindrome,
// so we can go to check the next characters
while (l >= 0 && r < s.size() && s[l] == s[r]) {
l--;
r++;
}
return s.substr(l + 1, r - l - 1);
}
};
Top comments (0)