Leetcode 131.分割回文串

力扣传送门(opens new window)

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例: 输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ]

解题思路：

结束条件：

当 index 的值等于字符串 str 的长度时，表示我们已经遍历完了整个字符串，没有剩余的字符可以继续回溯。在这种情况下，我们可以将当前列表中的回文子串组合加入结果列表 res，因为这个列表已经包含了一个有效的回文子串组合。

考虑一个例子来说明这个结束条件的使用：

假设输入字符串是 "aab"。

1. 开始时，index = 0，我们将 "a" 加入列表 list，然后递归调用 backTracking 方法，并增加 index 的值。
2. 当 index = 1 时，我们将 "a" 加入列表 list，然后递归调用 backTracking 方法，并增加 index 的值。
3. 当 index = 2 时，我们将 "b" 加入列表 list，然后递归调用 backTracking 方法，并增加 index 的值。
4. 当 index = 3 时，满足结束条件，我们将列表 list 加入结果列表 res。

以下是解题的详细思路：

1. 创建一个列表 res 来存储最终的结果，每个结果是一个回文子串组合。
2. 创建一个列表 list 来存储当前的回溯路径，表示当前的回文子串组合。
3. 调用 backTracking 方法进行回溯处理，传入初始参数 s、0（表示从字符串的开头开始遍历）和空的列表 list。
4. 在 backTracking 方法中，首先判断终止条件。当遍历到字符串的结尾时，将当前列表中的回文子串组合加入结果列表 res 中，然后返回。
5. 在回溯的过程中，我们需要遍历从当前位置 index 到字符串末尾的所有子串，其中 index 初始值为传入的参数 index。
6. 对于每个子串，我们检查它是否是回文字符串。如果是回文字符串，我们将它加入当前列表 list 中，并递归调用 backTracking 方法，从当前子串的下一个位置开始继续回溯。
7. 在递归调用返回后，我们需要进行回溯操作，将当前子串从列表 list 中移除，以尝试其他可能的回文子串组合。

数形结合：

代码实现：

class Solution {
    // 存储结果的列表
    List<List<String>> res = new ArrayList();  

    public List<List<String>> partition(String s) {
        if (s == null || s.length() == 0) {
            return res;
        }
        // 存储当前回溯路径的列表
        List<String> list = new ArrayList();  
        backTracking(s, 0, list);  
        return res;
    }

    public void backTracking(String s, int index, List<String> list) {
        // 终止条件：当遍历到字符串的结尾时，将当前列表中的回文子串组合加入结果列表中
        if (index == s.length()) {
            res.add(new ArrayList(list));
            return;
        }
        //这里要理解为什么从index开始
        for (int i = index; i < s.length(); i++) {
                // 如果从索引index到i的子串是回文字符串，则将其加入当前列表
            if (isPalindromicString(s, index, i)) {
                list.add(s.substring(index, i + 1));
            } else {
                // 如果不是回文字符串，则继续遍历下一个子串
                continue;  
            }
            // 递归调用，从当前子串的下一个位置开始继续回溯
            backTracking(s, i + 1, list);  
            // 回溯，将当前子串从列表中移除，尝试其他可能的回文子串组合
            list.remove(list.size() - 1);  
        }
    }

    public boolean isPalindromicString(String str, int start, int end) {
        // 判断从索引start到end的子串是否是回文字符串
        while (start <= end) {
            char ch1 = str.charAt(start);
            char ch2 = str.charAt(end);
            if (ch1 != ch2) {
                // 如果不相等，则不是回文字符串
                return false;  
            }
            start++;
            end--;
        }
        // 如果全部字符相等，则是回文字符串
        return true;  
    }
}

注意：

substring的用法：

String str = "Hello, World!";
String sub1 = str.substring(7); // 从索引 7 开始提取子串，结果为 "World!"
String sub2 = str.substring(0, 5); // 从索引 0 到索引 5（不包括 5）提取子串，结果为 "Hello"

为什么for循环i从index开始？

回溯算法的思想是尝试所有可能的选择，并在每个选择上递归地进行下一步操作。在这个问题中，我们需要找到所有可能的回文子串组合，那么我们需要考虑从当前位置 index 开始到字符串末尾的所有子串。

假设我们有一个字符串 "aab"，如果我们从一直使得 i 从0 开始遍历，那我们一直从0开始切割，没有办法继续往后面切割了，我们的上一道题是 电话号码的字母组合 ，因为上道题是需要穷举每一种可能，ad,ae,af,但是这道题不一样，我们一旦切割完a之后，我们就不需要再次切割a，继续往后切割就可以，否则就会导致重复的结果~