回溯 04

眼若繁星丶 · 简书 · · 2021-03-07 11:42

回溯 04

LeetCode 131

https://leetcode-cn.com/problems/palindrome-partitioning/

回溯算法

图源：liweiwei1419

前缀字符串是回文，则可以引申出分支
前缀字符串不是回文，就可以剪枝，达到加速的目的
搜索的过程的路径用 path 来记录，因为 path 在最后结算时才使用，同时搜索也是采用DFS，所以 path 的数据结构采用栈更符合实际情况。在最后将 path 插入到结果 res 中时，要记得创建新的引用，即 res.add(new ArrayList<>(path)); 否则在回溯回去的下一个合法答案会修改原 path ，这点在回溯算法中很关键。

注：在中途操作过程中， path 要使用 addLast() 和 removeLast() ，这样记录的路径才是符合从前往后的顺序，可以试试使用 push() 和 pop() 来实现，会发现答案是从底向上，正好与实际情况相反。
push() 底层实现是 addFirst() ; pop() 底层实现是 removeFirst() 。

代码如下：

public List<List<String>> partition(String s) {
    List<List<String>> res = new ArrayList<>();
    int len = s.length();
    if (len == 0) return res;
    Deque<String> stack = new ArrayDeque<>();
    DFS(s.toCharArray(), 0, len, stack, res);
    return res;
}

    /**
     * @param charArray
     * @param startIdx 起始下标
     * @param len 字符串长度，用来判断搜索是否到头
     * @param path 保存路径
     * @param res 保存所有合法结果
     */
public void DFS(char[] charArray, int startIdx, int len, Deque<String> path, List<List<String>> res) {
    if (startIdx == len) {
        res.add(new ArrayList<>(path));
        return;
    }
    for (int i = startIdx; i < len; i++) {
        if (!isValid(charArray, startIdx, i)) {
            continue;   // 剪枝
        }
        // public String(char value[], int offset, int count) - offset起始下标，count偏移的长度
        path.addLast(new String(charArray, startIdx, i - startIdx + 1));
        DFS(charArray, i + 1, len, path, res);  // startIdx要从 i + 1位置开始，而不是startIdx + 1
        path.removeLast(); // 回溯，还原状态
    }
}

    /**
     * 判断是否在区间内为回文子串
     * @param charArray
     * @param left 左边界
     * @param right 右边界
     * @return
     */
private boolean isValid(char[] charArray, int left, int right) {
    while (left < right) {
        if (charArray[left] != charArray[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}