131.Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

Analyze

本题为回溯法的典型案例。

• a
  • a
    • b √
  • ab
• aa
  • b √
• aab

/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function(s) {
  const result = []
  partitionSub(s, 0, [], result)
  return result
};

var partitionSub = function(s, start, arr, result) {
  if (arr.join('').length === s.length) {
    result.push([...arr])
    return
  }
  for (let i = start + 1; i <= s.length; i++) {
    const curSubString = s.slice(start, i)
    if (ifPalindrome(curSubString)) {
      arr.push(curSubString)
      partitionSub(s, i, arr, result)
      arr.pop() // key code for back track
    } else {
      continue
    }
  }
}

// judge if it's palindrome
var ifPalindrome = function(curSubString) {
  return curSubString === curSubString.split('').reverse().join('')
}

推荐指数

※※※※※

相关问题

46