131. Palindrome Partitioning

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.

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:

class Solution {

    /**
     * @param String $s
     * @return String[][]
     */
    function partition($s) {
        $length = strlen($s);
        $palindromeTable = array_fill(0, $length, array_fill(0, $length, true));
        for ($i = $length - 1; $i >= 0; $i--) {
            for ($j = $i + 1; $j < $length; $j++) {
                $palindromeTable[$i][$j] = ($s[$i] == $s[$j]) && $palindromeTable[$i + 1][$j - 1];
            }
        }

        $result = array();
        $tempPartition = array();
        $depthFirstSearch = function($start) use (&$depthFirstSearch, &$result, &$tempPartition, $s, $length, $palindromeTable) {
            if ($start == $length) {
                $result[] = $tempPartition;
                return;
            }
            for ($end = $start; $end < $length; $end++) {
                if ($palindromeTable[$start][$end]) {
                    $tempPartition[] = substr($s, $start, $end - $start + 1);
                    $depthFirstSearch($end + 1);
                    array_pop($tempPartition);
                }
            }
        };
        $depthFirstSearch(0);
        return $result;
    }
}

Contact Links

• LinkedIn
• GitHub

---

1. Substring A substring is a contiguous non-empty sequence of characters within a string. ↩

2. Palindrome A palindrome is a string that reads the same forward and backward. ↩