LeetCode 131. 分割回文串

Question

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

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

示例:

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

---

前置知识

• 回溯法

公司

• 阿里
• 腾讯
• 百度
• 字节

思路

这是一道求解所有可能性的题目， 这时候可以考虑使用回溯法。 回溯法解题的模板我们已经在很多题目中用过了， 这里就不多说了。大家可以结合其他几道题目加深一下理解。

这种题目其实有一个通用的解法，就是回溯法。网上也有大神给出了这种回溯法解题的 通用写法，这里的所有的解法使用通用方法解答。 除了这道题目还有很多其他题目可以用这种通用解法，具体的题目见后方相关题目部分。

这里我画了一个图：

图是 78.subsets，都差不多，仅做参考。

关键点解析

• 回溯法

代码

• 语言支持：JS，Python3, CPP

JS Code:

/*
 * @lc app=leetcode id=131 lang=javascript
 *
 * [131] Palindrome Partitioning
 */

function isPalindrom(s) {
  let left = 0;
  let right = s.length - 1;

  while (left < right && s[left] === s[right]) {
    left++;
    right--;
  }

  return left >= right;
}
function backtrack(s, list, tempList, start) {
  const sliced = s.slice(start);

  if (isPalindrom(sliced) && tempList.join("").length === s.length)
    list.push([...tempList]);

  for (let i = 0; i < sliced.length; i++) {
    const sub = sliced.slice(0, i + 1);
    if (isPalindrom(sub)) {
      tempList.push(sub);
    } else {
      continue;
    }
    backtrack(s, list, tempList, start + i + 1);
    tempList.pop();
  }
}
/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function (s) {
  // "aab"
  // ["aa", "b"]
  // ["a", "a", "b"]
  const list = [];
  backtrack(s, list, [], 0);
  return list;
};

Python Code:

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        """回溯法"""

        res = []

        def helper(s, tmp):
            """
            如果是空字符串，说明已经处理完毕
            否则逐个字符往前测试，判断是否是回文
            如果是，则处理剩余字符串，并将已经得到的列表作为参数
            """
            if not s:
                res.append(tmp)
            for i in range(1, len(s) + 1):
                if s[:i] == s[:i][::-1]:
                    helper(s[i:], tmp + [s[:i]])

        helper(s, [])
        return res

CPP Code:

    class Solution {
private:
  vector<vector<string>> ans;
  vector<string> tmp;
  bool isPalindrome(string &s, int first, int last) {
    while (first < last && s[first] == s[last]) ++first, --last;
    return first >= last;
  }
  void dfs(string &s, int start) {
    if (start == s.size()) { ans.push_back(tmp); return; }
    for (int i = start; i < s.size(); ++i) {
      if (isPalindrome(s, start, i)) {
        tmp.push_back(s.substr(start, i - start + 1));
        dfs(s, i + 1);
        tmp.pop_back();
      }
    }
  }
public:
  vector<vector<string>> partition(string s) {
    dfs(s, 0);
    return ans;
  }
};

相关题目

• 39.combination-sum
• 40.combination-sum-ii
• 46.permutations
• 47.permutations-ii
• 78.subsets
• 90.subsets-ii
• 113.path-sum-ii