[ 回溯 ] 分割回文串_problem p26. [算法课回溯]分割回文串

131. 分割回文串 - 力扣（LeetCode） (leetcode-cn.com)

分割回文串

• 与数组组合不同的是，数组是取数，该题是找分割线

class Solution {
public:
    // 返回值
    vector<vector<string>> ans;
    vector<string> path;
    
    // DFS
    void DFS(string& s, int index) {
        // 边界
        if (index >= s.size()) {
            ans.emplace_back(path);
            return;
        }
        for (int i = index; i < s.size(); ++i) {
            // 数组是找到一个数，就进入下一层
            // 而字符串是必须找到一个回文串，才能继续下一层分割，所以才有continue语句
            if (isPalindrome(s, index, i)) {
                string str = s.substr(index, i - index + 1);
                path.emplace_back(str);
            }
            else {
                continue;
            }
            DFS(s, i + 1);
            path.pop_back();
        }
    }
	
    // 判断回文串
    bool isPalindrome(string& s, int start, int end) {
        for (int i = start, j = end; i < j; ++i, --j) {
            if (s[i] != s[j]) return false;
        }
        return true;
    }

    vector<vector<string>> partition(string s) {
        DFS(s, 0);
        return ans;
    }
};
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