Leetcode-131-分割回文串

Leecode-131-Palindrome Partitioning

思路：回溯+剪枝

题目描述

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

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

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

Solution：回溯

• 每一个结点表示剩余没有扫描到的字符串，产生分支是截取了剩余字符串的前缀；

• 判断前缀字符串是不是回文串

  • 是，则可以产生分支和节点
  • 不是，进行剪枝

• 当叶子节点是空字符串的时候，返回从根节点到叶子节点的路径，当做一个结果集

• 最后用一个总的结果集包含上述一个个的结果集

废话如下：

• 采用一个路径变量 path 搜索，path 全局使用一个（注意结算的时候，需要生成一个拷贝
• 因此在递归执行方法结束以后需要回溯，即将递归之前添加进来的元素拿出去；
• path 的操作只在列表的末端，因此合适的数据结构是栈。

Java

Solution :

class Solution {
    public List<List<String>> partition(String s) {
        int len = s.length();
        // 存放最终结果
        List<List<String>> res = new ArrayList<>();

        if (len == 0){
            return res;
        }

        // Stack这个类Java文档里推荐写成
        // Deque<Integer> stack = new ArrayDeque<Integer>();
        Deque<String> stack = new ArrayDeque<>();
        backtracking(s,0,len,stack,res);
        return res;
    }

    /**
     *
     * @param s     传入的字符串
     * @param start 起始字符的索引
     * @param len   字符串s的长度
     * @param path  记录从根节点到叶子节点的路径
     * @param res   记录所有的结果
     */

    private void backtracking(String s, int start, int len, Deque<String> path, List<List<String>> res) {
        // 达到最大深度，返回结果
        if (start == len){
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < len; i++) {
            // 前缀字符串不是回文
            if (!isPalindrome(s,start,i)){
                // 剪枝退出本轮循环
                continue;
            }
            // 前缀字符串是回文，把前缀加到结果
            path.addLast(s.substring(start,i + 1));
            // 向下判断
            backtracking(s,i + 1,len,path,res);
            // 回溯操作
            path.removeLast();
        }
    }

    // 判断是否回文串
    private boolean isPalindrome(String s,int left,int right){
        while (left < right){
            if (s.charAt(left) != s.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

• 时间复杂度：O(logn) 栈的深度
• 空间复杂度：O(logn) 栈的深度

测试用例：

public static void main(String[] args) {
    Solution solution = new Solution();
    System.out.println(solution.getMoneyAmount(10));
}

Python

Solution :

打赏