131. Palindrome Partitioning
Medium
Given a string s
, partition s
such that every substring1 of the partition is a palindrome2. 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
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!