Leetcode - 131. Palindrome Partitioning

문제

주어진 문자열을 파티셔닝 한다고 할때, 나눈 sub문자열이 모두 palindrome인 경우를 모두 출력하라.

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

해결

백트래킹, for문을 돌며 cur 부터 i길이만큼 문자를 확인하고 그 뒤 문자열은 재귀적으로 체크. 추가로 s.substr(시작 인덱스, 길이) 두번재 인자가 길이임 주의.

class Solution {
    vector<vector<string>> ret;
    vector<string> tmp;
    
    bool is_palindrome(string s) {
        int ssize = s.length();
        for (int i = 0; i < ssize / 2; i++) {
            if (s[i] != s[ssize - i - 1])
                return false;
        }
        return true;
    }
    void recur(string s, int cur) {
        if (cur >= s.length()) {
            ret.push_back(tmp);
            return;
        }
        
        for (int i = cur; i < s.length(); i++) {
            string tgt = s.substr(cur, i-cur+1);
            if (!is_palindrome(tgt))
                continue;
            tmp.push_back(tgt);
            recur(s, i+1);
            tmp.pop_back();
        }
    }
public:
    vector<vector<string>> partition(string s) {
        recur(s, 0);
        return ret;
    }
};