[Backtracking][Medium] 131. Palindrome Partitioning

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

Palindrome Partitioning - LeetCode

 

Q. 주어진 문장 s 에 대해, 파티션으로 문자를 나눈다. 이때 이 나눠진 문자(sub string) 모두가 palindrome (앞으로 뒤로 읽어도 같음) 이 되는 대상들을 찾아라.

 

Solution. 

 파티션을 나눈다는 개념이 조금 일반적이지는 않지만, 모든 배열의 원소를 순회하여 비교해야 하는 개념에서 backtrack을 써야 함을 알 수 있다. 

 파티션을 나눈다는 것을 다시 생각해 보면, 

 현재 위치에서 1개 부터 남은 수 만큼 늘려가며 포함해 보면 결국 파티션을 나누는 개념과 동일함을 알 수 있다. 

 

 그러면, 파티션을 나눌 수 있게 되었다.

 파티션의 어떤 대상을 backtrack하나? 

 파티션된 대상이 palindrome 할 때만 하면 될 것이다. 

 그렇다면 종료 조건은?

 더이상 나눌 파티션이 없으면 종료 하면 될 것이다. 

 

 로직대로 코드를 만들어 본다. 

 

 

bool isPalindrome(string& strInput)
{
    for (int k = 0; k <= strInput.size() / 2; ++k)
    {
        if (strInput[k] != strInput[strInput.size() - k - 1])
            return false;
    }
    return true;
}
void partition_BT(vector<vector<string>>& vOut, string& s, vector<string>& vCur, int idx)
{
    if (idx >= s.size())
    {
        vOut.push_back(vCur);
        return;
    }

    // 하나씩, 남은 수 만큼 substring 하면 그것이 파티션 하는 것이 된다.
    for (int k = 1; k <= s.size()-idx; ++k)
    {
        string built = s.substr(idx, k);
        if (isPalindrome(built))
        {
            vCur.push_back(built);
            partition_BT(vOut, s, vCur, idx+k);
            vCur.pop_back();
        }
    }
}

vector<vector<string>> partition(string s) 
{
    vector<vector<string>> vOut;
    vector<string> vCur;
    partition_BT(vOut, s, vCur, 0);
    return vOut;
}

 

적당한 결과를 얻었다.