leetcode 131. Palindrome Partitioning

佚名 6年前 (2019-04-13) 随笔 2179人围观抢沙发百度已收录

131. Palindrome Partitioning

substr使用的是坐标值，不使用.begin()、.end()这种迭代器

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

使用dfs，类似于subsets的题，每次判断要不要加入这个数

start每次是起始的位置，判断当前位置到起始位置是不是回文

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string> > result;
        if(s.empty())
            return result;
        vector<string> res;
        int start = 0;
        partition(s,result,res,start);
        return result;
    }
    void partition(string s,vector<vector<string>>& result,vector<string>& res,int start){
        if(start == s.size()){
            result.push_back(res);
            return;
        }
        for(int i = start;i < s.size();i++){
            if(!ispalindrome(s,start,i))
                continue;
            res.push_back(s.substr(start,i - start + 1));
            partition(s,result,res,i+1);
            res.pop_back();
        }
    }
    
    bool ispalindrome(string s,int start,int end){
        while(start < end){
            if(s[start++] != s[end--])
                return false;
        }
        return true;
    }
};