分割回文串

link：131. 分割回文串 - 力扣（LeetCode）

思路分析

主题思想是和之前做的组合II相同的，问题的关键难点就是在怎么处理切割上.
首先递归参数传入startIndex是表示下一轮递归遍历起始位置，那么startIndx就是作为我们的切割线一角色.
再看回文子串如何判断？采用双指针法，一个在头一个在尾前后指针指向位置的元素相等就是回文串了.

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
class Solution {
    List<List<String>> res = new ArrayList<>();
    Deque<String> deque = new LinkedList<>();
    public List<List<String>> partition(String s) {
        backtracking(s,0);
        return res;
    }
    private void backtracking(String s, int startIndex) {
        //起始位置大于s的长度->找到了一组分割方案
        if(startIndex >= s.length()) {
            res.add(new ArrayList(deque));
            return;
        }
        for(int i = startIndex;i < s.length(); i++) {
            //记录回文串
            if(isPalindrome(s,startIndex,i)) {
                String str = s.substring(startIndex,i + 1);
                deque.addLast(str);
            }else {
                continue;
            }
            backtracking(s, i + 1);
            deque.removeLast();
        }
    }
    //判断是否是回文串
            private boolean isPalindrome(String s, int startIndex, int end) {
            for(int i = startIndex, j = end; i < j; i++,j--) {
                if(s.charAt(i) != s.charAt(j)) {
                    return false;
                }
            }
            return true;
        }
}

复原ip地址

link：

思路分析
1