131. Palindrome Partitioning

发表于 | 分类于

每日一题 2019 - 05 - 03

题目：

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

Return all possible palindrome partitioning of s.

Example:

1
2
3
4
5
6
Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

解法：

这个题让把给定的字符串有限情况下分割成尽可能多情况的子回文序列，所以思路就是深度优先搜索，从字符串的开头出发，每次都往后搜索一位，在到达字符串末尾时候，一层层跳出当前的嵌套循环中，并增加一个递归的字符长度，继续进行往后遍历；

同时需要对当前待进行分割字符串进行判断，判断其是否是回文序列；

代码：

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
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<string> now ;
        vector<vector<string>> temp ;
        if(s.size() == 0)
        {
            return temp ;
        }
        find(temp,now,0,s);
        return temp ;
    }
    void find(vector<vector<string>>& temp , vector<string>& now,int n , string s)
    {
        if(n == s.size())
        {
            temp.push_back(now);
            return ;
        }
        for(int i = n ; i < s.size() ; i ++ )
        {
            if(istrue(s.substr(n,i-n+1)))
            {
                now.push_back(s.substr(n,i-n+1));
                find(temp,now,i+1,s);
                now.pop_back();
            }
        }
    }
    bool istrue(string s)
    {
        int size = s.size();
        for(int i = 0 ; i < size ; i ++ )
        {
            if(s[i] == s[size - 1 - i])
            {
                continue ;
            }
            else
            {
                return false ;
            }
        }
        return true ;
    }
};
0%
undefined