回溯 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;
}

题解参考：https://leetcode-cn.com/problems/palindrome-partitioning/solution/hui-su-you-hua-jia-liao-dong-tai-gui-hua-by-liweiw/