가장 긴 회문 하위 문자열 - 파트 2

어제는 팰린드롬 데이! 22022022!

그리고 this post에서 Leetcode에 대한 회문 하위 문자열 문제에 대해 이야기한 것을 기억합니다. 나는 그것을 해결하기 위해 Manacher's Algorithm을 사용했다. 효율적이지만 한 번에 제대로 하기는 정말 어렵습니다. 특히 나를 위해 :(

쉬운 방법

그래서 여기에 훨씬 더 쉬운 버전이 있지만 매우 효율적이지는 않습니다. 그러나 이해하고 작성하는 것이 정말 쉽습니다. 나는 첫 시도에서 그것을 맞았다.

아이디어는 문자열의 각 문자에서 왼쪽과 오른쪽으로 이동하는 두 개의 인덱스(포인터)를 사용하여 두 문자가 다를 때까지 두 문자를 확인하는 것입니다. 예를 들어 문자열의 경우

"b c d e f e d g h i"



파란색 화살표는 문자열의 각 문자를 살펴보고 있음을 나타내고 빨간색 화살표는 각 문자에서 시작하여 매번 왼쪽과 오른쪽으로 한 단계씩 이동하여 현재 문자가 동일한지 확인하는 두 개의 포인터를 나타냅니다. 동일하다면 현재 회문 문자열이 있으므로 다음 왼쪽 및 오른쪽 문자를 확인할 수 있습니다.

또한 짝수 문자의 경우에 대해서도 생각해야 합니다.



전체 문자열과 문자 인덱스(파란색 화살표가 가리키는)가 매개변수로 주어지면 회문 하위 문자열을 반환하는 함수를 작성할 수 있습니다.

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);
}

홀수개의 문자가 있는 문자열의 경우 l = r 로 함수를 호출하십시오. 그렇지 않으면 "짝수 문자열"의 경우 r = l + 1
해결책은 아래와 같습니다. 42ms, 22.7MB.

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);
    }
};