leetcode hard : Shortest Palindrome

https://leetcode.com/problems/shortest-palindrome/description/

Shortest Palindrome - LeetCode

 

이건 어려워서 솔루션 보고 학습을 진행했다.

일단 이 포스팅에서 KMP알고리즘은 설명하지 않을건데 (나도 너무 어렵다 이건)

나도 kmp는 아직 잘 모르기 때문이다. 얼추 이해하긴 했는데 아직 완벽히는 모르겠다.

KMP 공부 참고자료

https://www.youtube.com/watch?v=UcjK_k5PLHI 

https://www.youtube.com/watch?v=yWWbLrV4PZ8 

 

그럼 Official Solution을 보고 학습을 해보자.

 

Approach 1 : Brute force [Time Limit Exceeded]

1. 문자열의 왼쪽에서 가장 큰 회문을 찾는다.

2. 찾은 회문을 제외하고 남은 오른쪽 파트를 뒤집는다.

 

Example

문자열 abac

* 왼쪽에서 찾은 가장 큰 회문 [aba]c => aba

* 찾은 회문 제외한 오른쪽 파트 aba[c] => c

* 앞에 c를 붙이면 회문이 된다. => cabac

 

Algorithm

1. 문자열을 뒤집는다. 이걸 r이라고 하자.

2. 문자열의 길이를 n이라고 하자.

3. 원본 문자열은 s다.

4. s[0:n-i] == r[i:]가 성립될때까지 i를 증가시킨다.

- 즉 처음엔 전체를 뒤집었을때 회문이 되는지 보는거고

- i가 증가함에 따라 맨 오른쪽에서 글자를 하나씩 제거하면서 그걸 뒤집은걸 비교하는거라고 봐도 된다.

5. i를 찾으면 r[:i]에 s를 붙여 리턴한다.

 

class Solution {
public:
    string shortestPalindrome(string s) {
        int n = s.size();
        string rev(s);
        reverse(rev.begin(), rev.end());
        for (int i = 0; i < n; i++) {
            if (s.substr(0, n - i) == rev.substr(i))
                return rev.substr(0, i) + s;
        }
        return "";
    }
};

 

Approach 2 : Two pointers and recursion [Accepted]

* i = 0

* j를 n-1 -> 0으로 iteration

  * s[i] == s[j]면 i++

* loop이 끝나고나면 s[:i]에 palindrome이 포함되어 있다.

* reversed(s[i:]) + recursion(s[:i]) + s[i:]가 정답

최상의 케이스는 s자체가 palindrome일때

최악은 "aababababababa" 이런경우

 

class Solution {
public:
    string shortestPalindrome(string s) {
        int n = s.size();
        int i = 0;
        for (int j = n - 1; j >= 0; j--) {
            if (s[i] == s[j])
                i++;
        }
        if (i == n) {
            return s;
        }
        string remain_rev = s.substr(i, n);
        reverse(remain_rev.begin(), remain_rev.end());
        return remain_rev + shortestPalindrome(s.substr(0, i)) + s.substr(i);
    }
};

 

복잡도

시간 : 최약의 경우 O(N^2)

공간 : O(N)

 

아 어렵다 세상에 똑똑이형들 너무많당