LeetCode-in-All

131. Palindrome Partitioning

Medium

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

A palindrome string is a string that reads the same backward as forward.

Example 1:

Input: s = “aab”

Output: [[“a”,”a”,”b”],[“aa”,”b”]]

Example 2:

Input: s = “a”

Output: [[“a”]]

Constraints:

• 1 <= s.length <= 16
• s contains only lowercase English letters.

Solution

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

const backtracking = (res, currArr, s, start) => {
    if (start === s.length) {
        res.push([...currArr])
        return
    }

    for (let end = start; end < s.length; end++) {
        if (!isPalindrome(s, start, end)) {
            continue
        }
        currArr.push(s.substring(start, end + 1))
        backtracking(res, currArr, s, end + 1)
        currArr.pop()
    }
};

const isPalindrome = (s, start, end) => {
    while (start < end && s[start] === s[end]) {
        start++
        end--
    }
    return start >= end
};

export { partition }

This site is open source. Improve this page.