[LeetCode] 214. Shortest Palindrome

https://leetcode.com/problems/shortest-palindrome/description/?envType=daily-question&envId=2024-09-20

leetcode - Shortest Palindrome

문제 유형 : 팰린드롬, 문자열 처리, KMP 알고리즘

문제 난이도 : Hard

 

문제

You are given a string s. You can convert s to a palindrome by adding characters in front of it.

Return the shortest palindrome you can find by performing this transformation.

 

문자열 s를 받는다. 당신은 s에 접두사를 붙여서 변환시킬 수 있다.

s에 문자를 붙여서 만들 수 있는 가장 짧은 팰린드롬의 길이를 구하시오.

 

풀이

KMP 알고리즘을 응용해서 문제를 해결할 수 있다.(참고)

 

새로운 문자열 temp = s + '#' + reverse(s)를 만든다.

temp에 대한 LPS 배열을 계산한다.

LPS 배열의 마지막 값은 S의 접두사이면서 Rev(S)의 접미사인 가장 긴 substring의 길이이다.

추가해야 하는 최소한의 접두사는 s의 역문자열의 앞부분 중(S의 길이 - LPS마지막 값)만큼이다.

 

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    string shortestPalindrome(string s) {
        string rev_s = s;
        reverse(rev_s.begin(), rev_s.end());
        string temp = s + "#" + rev_s;
        vector<int> lps(temp.size(), 0);
        
        for (int i = 1; i < temp.size(); ++i) {
            int len = lps[i - 1];
            while (len > 0 && temp[i] != temp[len]) {
                len = lps[len - 1];
            }
            if (temp[i] == temp[len]) {
                ++len;
            }
            lps[i] = len;
        }
        
        string add_on = rev_s.substr(0, s.size() - lps.back());
        return add_on + s;
    }
};