[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;
    }
    
};