131. 分割回文串

原题链接：LeetCode 131. 分割回文串

题目描述

给你一个字符串 s，请你将* s *分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。

示例 1：

**输入：**s = "aab" 输出：[["a","a","b"],["aa","b"]]

示例 2：

**输入：**s = "a" 输出：[["a"]]

提示：

- `1 <= s.length <= 16`

- `s` 仅由小写英文字母组成

难度： Medium

题解代码

javascript

/**
 * @param {string} s
 * @return {string[][]}
 */
// 跟复原ip地址很像
var partition = function(s) {
  const ret = []
  backtrack(s, ret, [])
  return ret
};

function backtrack (s, ret, path) {
  if (!s.length) {
    return ret.push([...path])
  }
  for(let i = 1; i < s.length + 1; i++) {
    const item = s.slice(0, i)
    if (!isValid(item)) continue
    path.push(item)
    s = s.slice(i)
    backtrack(s, ret, path)
    s = path.pop() + s
  }
}

function isValid (s) {
  let start = 0, end = s.length - 1
  for (i = start, j = end; i < j; i++, j--) {
    if (s[i] !== s[j]) return false
  }
  return true
}

// 来自题解 动态规划预处理 时间复杂度感觉优化不大
// var partition = function(s) {
//   const dfs = (i) => {
//       if (i === n) {
//           ret.push(ans.slice());
//           return;
//       }
//       for (let j = i; j < n; ++j) {
//           if (f[i][j]) {
//               ans.push(s.slice(i, j + 1));
//               dfs(j + 1);
//               ans.pop();
//           }
//       }
//   }
  
//   const n = s.length;
//   const f = new Array(n).fill(0).map(() => new Array(n).fill(true));
//   let ret = [], ans = [];
  
//   for (let i = n - 1; i >= 0; --i) {
//       for (let j = i + 1; j < n; ++j) {
//           f[i][j] = (s[i] === s[j]) && f[i + 1][j - 1];
//       }
//   }
//   dfs(0);
//   return ret;
// };

131. 分割回文串 #

题目描述 #

题解代码 #

131. 分割回文串

题目描述

题解代码