Palindrome Partitioning

본격적으로 DFS / BFS 를 넘어서 완전 탐색, Backtracking 류의 문제에 도전 해보고 있다. 일단 기본적으로 combination 과 permutation의 구현 정도는 쉽게 할 수 있다. 다만, Backtracking 을 내가 정말 알고 있나? 에서 이 문제에서 좀 좌절했다.

이 문제는 주어진 s 값에 substring이 palindrome 이 되는 모든 경우의 수를 반환해야 하는 문제다.

가장 처음에 각각의 캐릭터는 paldrome 이겠지만 이후에 substring 을 만드는 과정이 내가 backtracking 을 잘 모르고 있었기 때문에 너무 많이 헷갈린 느낌이었다.

다 풀었을때는 쉬웠지만 답을 참고했고 한번 리뷰해보는게 좋을 거같다.

class Solution {
public: 
    bool isPalindrome(string s){
        int start = 0, end = s.length() -1; 
        while(start <= end){
            if(s[start] != s[end]) return false; 
            start++;
            end--; 
        }
        return true; 
    }
    void dfs(vector<vector<string>>& answer, vector<string>& container, string s, int index){
        if(index >= s.length()){
            answer.push_back(container); 
        }

        for(int i = index; i < s.length(); i++){
            if(isPalindrome(s.substr(index, i - index + 1))){
                container.push_back(s.substr(index, i - index + 1));
                dfs(answer, container, s, i + 1); 
                container.pop_back(); 
            }
        }
    }
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> answer; 
        vector<string> container; 
        
        dfs(answer, container, s, 0); 

        return answer; 
    }
};