[Leetcode] 131. Palindrome Partitioning (C++)

문제

131. Palindrome Partitioning

코드

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> answer;
        vector<string> cur;
        
        dfs(answer, cur, s);
        return answer;
    }
    
    void dfs(vector<vector<string>>& answer, vector<string>& cur, string s){
        if (s == "") answer.push_back(cur);
        
        for (int i = 1; i <= s.length(); i++){
            string sb = s.substr(0, i);
            if (isPalindrome(sb)) {
                cur.push_back(sb);
                dfs(answer, cur, s.substr(i));
                cur.pop_back();
            }
        }
    }
    
    bool isPalindrome(string s){
        int lo = 0, hi = s.length()-1;
        while (lo < hi){
            if (s[lo] != s[hi]) return false;
            lo++; hi--;
        }
        return true;
    }
};

접근

먼저 주어진 문자열이 palindrome인지 아닌지 판단해야하기 때문에 이를 판단하는 메소드를 작성했다. 전체적인 접근은 문자열과 현재 substring들을 모아둔 배열을 유지하다가 해당 문자열이 빈 문자열인 경우까지 재귀로 돌아간다. 주어진 문자열에서 만들어낸 substring이 palindrome일 경우 재귀호출을 한다. 반복문에서 사용하는 변수 i는 살펴볼 문자의 개수이기 때문에 문자열의 길이와 같을 때까지 반복한다.