WEI-CHENG CHEN

說明：

這題的目標是把字串分割成「所有子字串皆為回文」的各種組合，考驗的是：遞迴拆解 + backtracking。

解法 01：backtracking

class Solution {
public:
    vector<vector<string>> ans;
    bool isPalindrome(string s){
        int left = 0;
        int right = s.size()-1;
        while(left<=right){
            if(s[left]!=s[right]) return false;
            left++;
            right--;
        }

        return true;
    }
    void backtrack(vector<string>& temp, string s, int index){
        // 停止條件
        if(index == s.size()){
            ans.push_back(temp);
            return;
        }
        for(int i=index;i<s.size();i++){
            // 檢查是否為回文
            bool flag = isPalindrome(s.substr(index, i-index+1));
            if(flag){
                temp.push_back(s.substr(index, i-index+1));
                backtrack(temp, s, i+1);
                temp.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string s) {
        vector<string> temp;
        backtrack(temp, s, 0);
        return ans;
    }
};

解法 02：DP

定義 dp[i][j] == true 代表子字串 s[i] 到 s[j] 是回文

• 如果dp[i][j] == true (也就是裡面那段是回文)
• 再加上 s[i] == s[j]
• 那就可以推出新的dp[i][j]也是回文

公式：dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]