回溯解决分割回文串问题_回溯策略回文串问题

题目描述

代码

class Solution {

    //存放最终结果
    List<List<String>> res = new ArrayList<>();
    //存放每次的结果
    Deque<String> path = new ArrayDeque<>();

    public List<List<String>> partition(String s) {
        //对空串判断
        if(s.length() == 0){
            return res;
        }
        //回溯处理
        backtracking(s,0);
        //返回结果
        return res;
    }

    public void backtracking(String s,int index){
        //结束条件判断
        if(index >= s.length()){
            //将符合条件的path加入最终结果res
            res.add(new ArrayList(path));
            return;
        }
        //for循环遍历字符串s
        for(int i = index;i < s.length();i++){
            //回文串判断
            if(isPalindrome(s,index,i)){
                //截取符合条件的字串
                String str = s.substring(index,i + 1);
                path.addLast(str);
            }else{
                continue;
            }
            //递归
            backtracking(s,i + 1);
            //回溯，撤回上一步操作
            path.removeLast();
        }
    }
    public boolean isPalindrome(String s,int i,int j){
        while(i < j){
            if(s.charAt(i) != s.charAt(j)){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

// //模板
// public void backtracking(参数){
//     if(终止条件){
//         保存结果;
//         return;
//     }
//     for(遍历字符串){
//         处理节点;
//         backtracking();
//         撤销上次操作;
//     }
// }
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65