sl1673495 / leetcode-javascript

:beers: 喝杯小酒,一起做题。前端攻城狮从零入门算法的宝藏题库,根据知名算法老师的经验总结了 100+ 道 LeetCode 力扣的经典题型 JavaScript 题解和思路。已按题目类型分 label,一起加油。
2.08k stars 344 forks source link

分割回文串-131 #67

Open sl1673495 opened 4 years ago

sl1673495 commented 4 years ago

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

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

示例:

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

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

思路

递归全排列

尝试所有的下标做起点,所有的下标作为终点,递归暴力判断。

/**
 * @param {string} s
 * @return {string[][]}
 */

let partition = function (s) {
  let n = s.length
  let ret = []
  let find = function (start, prev) {
    // 最少分割一个字符 最多分割到末尾前一位
    for (let i = 1; i <= n; i++) {
      let end = start + i
      let cur = s.substring(start, end)
      if (cur) {
        let res = prev.concat(cur)
        if (isPalindrome(cur)) {
          if (end === n) {
            ret.push(res)
          } else {
            find(start + i, res)
          }
        }
      }
    }
  }
  find(0, [])
  return ret
}

function isPalindrome(s) {
  if (!s) {
    return false
  }
  let i = 0
  let j = s.length - 1

  while (i < j) {
    let head = s[i]
    let tail = s[j]

    if (head !== tail) {
      return false
    } else {
      i++
      j--
    }
  }
  return true
}