[LeetCode]131. Palindrome Partitioning

发表于 | 更新于: | 分类于 | | 阅读次数:

Problem

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

Return all possible palindrome partitioning of s.

Example:

Input: “aab”

Output:

[

[“aa”,”b”],

[“a”,”a”,”b”]

]

Solution

解析

回溯法。解决方法和求字符串排列结果类似。这里因为是回文串，每次从0开始，回文串长度从1变化到str.size();尝试一次划分，如果划分结果是回文串，插入到划分结果中，如果不是，尝试下一个长度。终止条件是index指向字符串末尾’\0’. 值得注意的是，回溯法，最好调用递归之后，进行回溯,返回到原来的状态，否则，容易出错(没错就是你！)。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<vector<string>> partition(string s) {
        if (s.empty()) return {};
        vector<string> temp;
        vector<vector<string>> res;
        helper(s, 0, temp, res);
        
        return res;
    }
private:
    void helper(string str, int start, vector<string> &temp, vector<vector<string>> &res){
        if (start == str.size()){
            res.push_back(temp);
            //return; 去掉后，运行速度反而更快了，不太理解
        }
        for (int i = 1; i<= str.size()-start; ++i){
            if (judge(str.substr(start, i))){
                temp.push_back(str.substr(start, i));
                helper(str, start+i, temp, res);
                temp.pop_back();
            }   
        }
    }
    bool judge(string str){
        int lo = 0, hi = str.size() - 1;
        while (lo <= hi){
            if (str[lo] != str[hi]) return false;
            lo++; hi--;
        }
        return true;
    }
};
您的支持就是我更新的最大动力!谢谢!