【LeetCode】131.分割回文列結題報告(C++)

原題住所:https://leetcode-cn.com/problems/palindrome-partitioning/description/
タイトルの説明:
文字列sが与えられ、sはいくつかのサブストリングに分割され、各サブストリングがエコーストリングであるようにする.
sの可能なすべての分割スキームを返します.
例:
入力:「aab」出力:["aa","b",["a","a","b"]
 
問題解決方案:
本問題は遡及法の問題であり,遡及法は常に深さ優先遍歴に関係し,相関関数の命名はdfs()である.遍歴の方法は再帰であり,再帰的に伝達される重要なパラメータは現在の配列の開始位置である.
この問題では、現在の文字列が文列であるかどうかを判断し、関数isPali()を定義する必要があります.

class Solution {
public:
    bool isPali(string s){        
        for(int i = 0; i < s.length() / 2; i ++)         
            if(s[i] != s[s.length() - i - 1])                
                return false;         
        return true;    
    }

    
    void dfs(vector> &ans, vector &tmp, int n, string s){
        if(n == s.length()){
            ans.push_back(tmp);
            return;
        }
        for(int i = n; i < s.length(); i ++){
            if(isPali(s.substr(n, i - n + 1))){                
                tmp.push_back(s.substr(n, i - n + 1));                
                dfs(ans, tmp, i + 1, s);                
                tmp.pop_back();            
            }

        }
    }
    
    vector> partition(string s) {
        vector> ans;
        vector tmp;
        dfs(ans, tmp, 0, s);
        return ans;
    }
};