[LeetCode] 131、分割回文串

題目描述

給定一個字元串 s，将 s 分割成一些子串，使每個子串都是回文串。

傳回 s 所有可能的分割方案。

示例：

輸入: "aab"
輸出:
[
  ["aa","b"],
  ["a","a","b"]
]
           

解題思路

類似于46題的解法。（參考《劍指offer》上第197頁的思考過程）

參考1、參考2、參考3。

參考代碼

class Solution {
public:
    vector<vector<string> > partition(string str) {
        int length = str.size();
        vector<vector<string> > res;
        if(length == 0)
            return res;
        
        vector<string> subRes;
        partitionRecursively(str, 0, length, res, subRes);
        
        return res;
    }
    
    void partitionRecursively(string &str, int mStart, int length, vector<vector<string> > &res, vector<string> &subRes){
        if(mStart == length){   // 這個題這裡不能寫為 length - 1（字元串的全排列可以）
            res.push_back(subRes);
            return;
        }
        
        for(int i = mStart; i < length; i++){
            string tmpStr = str.substr(mStart, i - mStart + 1);
            if(isPalindrome(tmpStr)){
                subRes.push_back(tmpStr);
                partitionRecursively(str, i + 1, length, res, subRes);  // 注意這裡是 i+1
                subRes.pop_back();
            }
        }
        
    }
    
    bool isPalindrome(string &str){
        int low = 0, high = str.size() - 1;
        while(low <= high){
            if(str[low] != str[high])
                return false;
            low++, high--;
        }
        
        return true;
    }
    
};