[LeetCode] 131. Palindrome Partitioning

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

leetcode - Palindrome Partitioning

문제 유형 : 문자열 처리, 재귀, dfs, 백트래킹

문제 난이도 : Medium

 

문제

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

 

문자열 s가 주어진다.

모든 (s를 쪼갠 조각들이 팰린드롬 문자열)인 집합들을 반환하시오.

 

ex-> "aab"는 ["a", "a", "b"]로 나누면 모두 팰린드롬인 문자열들로 나눈 것입니다.

 

풀이

재귀적으로 풀 수 있다:

그 전에, 부분문자열이 팰린드롬인지 확인해야 하는데, 매번 구하기는 번거로우므로,

isPalindrome[시작인덱스][끝인덱스(닫힌구간)] = true/false의 값으로 저장시킨다.

우선isPalindrome[x][x], 즉 한 글자 짜리는 반드시 팰린드롬이다.

그리고, isPalindrome[x][x+1]즉 두 글자 짜리는 서로 비교를 해서 팰린드롬 여부를 저장시킨다.

 1글자, 2글자 짜리 부분문자열의 팰린드롬 여부는 다 파악이 끝났다.

이제 3글자 이상을 보면 되는데, 3글자 이상부터는 양 끝을 하나 자른 문자열의 팰린드롬 여부가 true이고, 양끝이 같으면, 계속 팰린드롬을 이어간다는 의미이다.

 

이제, 재귀로 조합들을 만들어보자.

기저 사례: 만약 이번에 넣을 부분문자열의 첫 인덱스가 n보다 크거나 같다면, 탐색이 끝났으므로, 현재의 파티션을 ans에 삽입한다.

 

아니라면, 현재 인덱스부터 n-1의 범위까지 부분문자열을 하나하나 만들어보고, 부분문자열인 경우, 현재의 파티션에 추가하여 재귀호출시킨다.

재귀호출이 끝나고 나면, 파티션에서 제거한다.

 

 

코드

C++

class Solution {
private:
    vector<vector<string>> ans;
    vector<vector<bool>> isPalindrome;
    int n;
public:
    void solve(string &s, vector<string> &substring_seq, int idx) {
        if(idx >= n) {
            ans.push_back(substring_seq);
            return;
        }
        for(int i = idx; i < n; i++) {
            string subs = s.substr(idx, i - idx + 1);
            if(isPalindrome[idx][i]) {
                substring_seq.push_back(subs);
                solve(s, substring_seq, i+1);
                substring_seq.pop_back();
            }
        }
    };

    vector<vector<string>> partition(string s) {
        n = s.size();
        vector<string> substring_seq = {};

        isPalindrome.resize(n, vector<bool>(n, false));
        for(int i = 0; i < n; i++) {
            isPalindrome[i][i] = true;
        }
        for(int i = 0; i < n - 1; i++) {
            if(s[i] == s[i + 1]) {
                isPalindrome[i][i + 1] = true;
            }
        }
        for(int length = 3; length <= n; length++) {
            for(int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                if(s[i] == s[j] && isPalindrome[i + 1][j - 1]) {
                    isPalindrome[i][j] = true;
                }
            }
        }

        solve(s, substring_seq, 0);
        return ans;
    }
};