LeetCode 131. 分割回文串

作者:Choi Yang

更新于:7 个月前

字数统计:692 字

阅读时长:3 分钟

题目描述

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

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

示例:

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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/palindrome-partitioning 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

借鉴 zesong-wang-c 大佬的图解

本题采用回溯思想，看上图基本已经明白，每次进行一次切割，直到切到最后一个元素，然后压入结果集合里，期间对于每次切割的字符串，我们判断一下是否是回文，如果不是，直接减掉即可。

和组合的思想有点类似。

javascript

// 判断是否是回文
function isPal(str) {
  let len = Math.floor(str.length / 2);
  if (len === 0) {
    return true;
  }
  let add = str.length % 2 === 0 ? 0 : 1;
  let subStr = str.slice(0, len);
  for (let i = 0; i < len; i++) {
    if (subStr[len - i - 1] !== str[len + add + i]) {
      return false;
    }
  }
  return true;
}
var partition = function (s) {
  let res = [];
  let dfs = (cur, start) => {
    // 当前已经到达了最后一个元素
    if (start >= s.length) {
      res.push(cur.slice());
      return;
    }
    for (let i = start; i < s.length; i++) {
      // 字符串切割
      let str = s.slice(start, i + 1);
      if (str && isPal(str)) {
        cur.push(str);
        dfs(cur, i + 1);
        // 回溯
        cur.pop();
      }
    }
  };
  dfs([], 0);
  return res;
};

cpp

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        vector<string> cur;
        function<bool(string)> isPal = <CustomLink title="&" href="string str" /> {
            int len = str.length();
            int add = len % 2 == 0 ? 0 : 1;
            len = len / 2;
            for (int i = 0; i < len; i++) {
                if (str[len - i - 1] != str[len + add + i]) {
                    return false;
                }
            }
            return true;
        };
        function<void(int)> dfs = <CustomLink title="&" href="int start" /> {
            if (start >= s.length()) {
                res.push_back(cur);
                return;
            }
            for (int i = start; i < s.length(); i++) {
                string str = s.substr(start, i - start + 1);
                if (isPal(str)) {
                    cur.push_back(str);
                    dfs(i + 1);
                    cur.pop_back();
                }
            }
        };
        dfs(0);
        return res;
    }
};

java

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        List<String> cur = new ArrayList<>();
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            Arrays.fill(dp[i], true);
        }
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i + 1; j < len; j++) {
                dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1];
            }
        }
        dfs(res, cur, dp, s, 0);
        return res;
    }

    private void dfs(List<List<String>> res, List<String> cur, boolean[][] dp, String s, int start) {
        if (start == s.length()) {
            res.add(new ArrayList<>(cur));
            return;
        }
        for (int i = start; i < s.length(); i++) {
            if (dp[start][i]) {
                cur.add(s.substring(start, i + 1));
                dfs(res, cur, dp, s, i + 1);
                cur.remove(cur.size() - 1);
            }
        }
    }
}

python

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res = []
        cur = []
        dp = [[True] * len(s) for _ in range(len(s))]
        for i in range(len(s) - 1, -1, -1):
            for j in range(i + 1, len(s)):
                dp[i][j] = s[i] == s[j] and dp[i + 1][j - 1]
        def dfs(start):
            if start == len(s):
                res.append(cur[:])
                return
            for i in range(start, len(s)):
                if dp[start][i]:
                    cur.append(s[start:i + 1])
                    dfs(i + 1)
                    cur.pop()
        dfs(0)
        return res

学如逆水行舟，不进则退

Contributors

Choi Yang