[C++]LeetCode: 121 Palindrome Partitioning (分割回文子串 回溯法)

题目:

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

思路:我们需要将一个字符串分割成回文子串的形式,然后返回所有的分割结果。需要两个辅助函数,一个是递归的DFS,帮助我们分割字符串,可以借鉴Restore IP Addresses的分割思想,我们循环所有的分割长度,从1开始直到剩余子串的长度(注意可以取等号i = s.size()),然后判断这个子串是否是回文,可以借鉴Valid Palindrome 中的方法,我们设置两个坐标从头尾判断,同时移动,如果有不相等返回false. 如果这个子串是回文,添加到tmp结果中,将剩余的字符串传给helper函数继续递归,直到剩余子串为空时,返回结果。重要的是,我们需要维护现场,将添加进去的子串结果pop_back出来。这样保证下次选择不同长度时,没有重复字符在结果中。

Attention:

1. 迭代终止条件,剩余子串长度为0.

if(s.size() == 0)
        {
            ret.push_back(tmp);
            return;
        }
2. 每次选择剩余子串进行递归。递归结束后,要维护现场。

int strlen = s.size();
                tmp.push_back(substr);
                partition_helper(s.substr(i, strlen - i), tmp, ret);
                tmp.pop_back();
3. i代表分割子串的长度,不是坐标,所以长度可以取字符串的长度。注意取等号。

for(int i = 1; i <= s.size(); i++)

复杂度:取决于结果的数量,最坏情况是指数量级的。

AC Code:

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> ret;
        if(s.size() == 0) return ret;
        vector<string> tmp;
        partition_helper(s, tmp, ret);
        return ret;
    }

private:
    void partition_helper(string s, vector<string> tmp, vector<vector<string>>& ret)
    {
        if(s.size() == 0)
        {
            ret.push_back(tmp);
            return;
        }
        
        for(int i = 1; i <= s.size(); i++)
        {
            string substr = s.substr(0, i);
            if(isPalindrome(substr))
            {
                int strlen = s.size();
                tmp.push_back(substr);
                partition_helper(s.substr(i, strlen - i), tmp, ret);
                tmp.pop_back();
            }
        }
    }
    
    //假设不含空格等其他字符,只含小写字母
    bool isPalindrome(string s) 
    {
        int len = s.size();
        if(len == 0 || len == 1) return true;
        int i = 0;
        int j = len - 1;
        
        while(i < j)
        {
            if(s[i++] != s[j--])
            {
                return false;
            }
        }
        return true;
    }
};





郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。