题目描述

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

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

示例

输入：

"aab"

输出：

[
  ["aa","b"],
  ["a","a","b"]
]

写在前面

本文答案参考自 LeetCode 网友 liweiwei1419 和 贝塔 的题解。

解法1：回溯

思路大体是：。。。哎呀，看代码吧[大哭]

代码

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public 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>();
    // 注意：只使用 stack 相关的接口
    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 (!checkPalindrome(s, start, i)) {
        continue;
      }

      path.addLast(s.substring(start, i + 1));
      backtracking(s, i + 1, len, path, res);
      path.removeLast();
    }
  }

  /**
   * 这一步的时间复杂度是 O(N)，因此，可以采用动态规划先把回文子串的结果记录在一个表格里
   *
   * @param str
   * @param left  子串的左边界，可以取到
   * @param right 子串的右边界，可以取到
   * @return
   */
  private boolean checkPalindrome(String str, int left, int right) {
    // 严格小于即可
    while (left < right) {
      if (str.charAt(left) != str.charAt(right)) {
        return false;
      }
      left++;
      right--;
    }
    return true;
  }
}

作者：liweiwei1419
链接：https://leetcode-cn.com/problems/palindrome-partitioning/solution/hui-su-you-hua-jia-liao-dong-tai-gui-hua-by-liweiw/
来源：力扣（LeetCode）

解法2：动态规划

答案的一个元素为一个回文串组

对一个回文串组，遍历 s的字符，当前字符 能加入到回文串组的情况有以下3种情况。

• 该回文串组为空
• 回文串组的最后一项为单字符且与当前字符相同
• 回文串组拥有两项以上，且倒数第二项与当前字符相同（此时倒数第二项必定只有一个字符）

代码

class Solution:
  def partition(self, s: str) -> List[List[str]]:
    if s == "":
      return []
    ans = [[s[0]] ]
    for i in range(1, len(s)):
      curr = s[i]
      newAns = []
      for item in ans:
        newAns.append(item + [curr])
        if item[-1] == curr:
          newAns.append(item[0:-1] + [item[-1] + curr])
        if len(item) >= 2 and item[-2] == curr:
          newAns.append(item[0:-2] + [item[-2] + item[-1] + curr])
      ans = newAns 
    return ans

作者：bei-ta-s
链接：https://leetcode-cn.com/problems/palindrome-partitioning/solution/chao-jian-dan-yi-dong-de-dong-tai-gui-hua-fa-by-be/
来源：力扣（LeetCode）