Palindrome Partitioning

Problem

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 = [];
    backtrack(res, 0, [], s);
    return res;
};

var backtrack = function(res, start, path, s) {
    if (start === s.length) {
        res.push([...path]);
    } else {
        for (let i = start; i < s.length; i++) {
            if (isPalindrome(s, start, i)) {
                path.push(s.substring(start, i + 1));
                backtrack(res, i + 1, path, s);
                path.pop();
            }
        }
    }
};

var isPalindrome = function(s, l, r) {
    while (l < r) {
        if (s[l++] !== s[r--]) {
            return false;
        }
    }
    return true;
};

We will implement a backtracking (DFS) solution. Essentially, we try all possible substring partition of s and slowly build up res. If the current substring from s[start:i + 1] is a palindrome, we add it to path, and recursively try to find a substring partition for the rest of s (ie. s[i + 1:s.length]). Once we reach the end of s, we push our valid partition path into res and backtrack.

For example, if s = "aaa", the recursion tree can be illustrated as follows:

Problem​

Solution​

Problem

Solution