[BackTrack][Medium] 131. Palindrome Partitioning

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

 

문자열이 주어질 때, palindrome한 sub string의 모음을 찾아라.

 

 

BackTrack의 원리 자체는 같지만, 구성과 진행 조건이 조금 다르다. 

 

실제로 string을 cut 해 보며 이것이 palindrome인지 확인하고, 그럴 때만 진행해 나간다.

 

나머지 조건은 대동소이 하다.

 

코드

 bool IsPalindrome(const string& s)
{
    if (s.size() <= 1)
        return true;
    int mid = s.size() / 2;
    for (int q = 0; q < mid; ++q)
    {
        if (s[q] != s[s.size() - q - 1])
            return false;
    }
    return true;
}
void partitionBT(vector<vector<string>>& vRet, vector<string>& vCur, const string& s, int idx)
{
    if (idx >= s.size())
    {
        vRet.push_back(vCur);
        return;
    }

    for (int q = idx; q < s.size(); ++q)
    {
        string cur = s.substr(idx, q-idx+1);
        if (IsPalindrome(cur))
        {
            // cout << cur << endl;
            vCur.push_back(cur);
            partitionBT(vRet, vCur, s, q+1);
            vCur.pop_back();
        }
    }
}

vector<vector<string>> partition(string s) 
{
    vector<vector<string>> vRet;
    vector<string> vCur;
    partitionBT(vRet, vCur, s, 0);
    return vRet;
}

 

결과