分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

方法：回溯

算法思路：

切割问题类似于组合问题，例如对于字符串abcdef：

  • 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中在选组第三个……。
  • 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中在切割第三段……。

  1. 确定递归函数参数

    除了输入的字符串s外，还需设置startIndex记录切割过的位置，不能重复切割。

  2. 确定终止条件

    当切割线到字符串最后面，即startIndex == s.size()时，终止递归。

    if(startIndex == s.length()){
                result.add(new ArrayList<>(path));
                return;
            }

  3. 编写判断是否为回文串的代码

    public boolean isPalindrome(String s, int startIndex, int end){
        while(startIndex < end){
            if(s.charAt(startIndex++) != s.charAt(end--)){
                return false;
            }
        }
        return true;
    }

  4. 单层搜索的过程

    判断startIndex到i的子串是否为回文串，若是则加到path中，否则continue结束本次for循环。

代码实现：

class Solution {
    public List<List<String>> result = new ArrayList<>();
    public LinkedList<String> path = new LinkedList<>();

    public List<List<String>> partition(String s) {
        backTracking(s, 0);
        return result;
    }

    public void backTracking(String s, int startIndex){
        if(startIndex == s.length()){
            result.add(new ArrayList<>(path));
            return;
        }

        for(int i = startIndex; i < s.length(); i++){
            if(isPalindrome(s, startIndex, i)){
                String str = s.substring(startIndex, i + 1);    //substring不要写错了
                path.add(str);
            }else{
                continue;
            }
            backTracking(s, i + 1);
            path.removeLast();
        }
    }

    public boolean isPalindrome(String s, int startIndex, int end){
        while(startIndex < end){
            if(s.charAt(startIndex++) != s.charAt(end--)){
                return false;
            }
        }
        return true;
    }
}

参考

代码随想录 - 分割回文串