131. Palindrome Partitioning

Problem

https://leetcode.com/problems/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.

For example, given s = "aab",

Return

[
  ["aa","b"],
  ["a","a","b"]
]

Solution

Still DFS.

For s[i], cache every palindrome that starts with s[i].

/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function(s) {

    var result = []

    function findPalindrome (start, res, s, cache) {
        if (start === s.length) {
            result.push(res.slice())
            return
        }

        if (cache[start]) {
            cache[start].forEach(end => {
                res.push(s.slice(start, end+1))
                findPalindrome(end+1, res, s, cache)
                res.pop()
            })
            return
        }

        cache[start] = []
        for (let end = start; end < s.length; end += 1) {
            if (isPalindrome(s, start, end)) {
                cache[start].push(end)
                res.push(s.slice(start, end+1))
                findPalindrome(end+1, res, s, cache)
                res.pop()
            }
        }
    }

    function isPalindrome(s, start, end) {
        while (start < end) {
            if (s[start++] !== s[end--]) {
                return false
            }
        }
        return true
    }

    findPalindrome(0, [], s, {})

    return result
};