DEV Community

MD ARIFUL HAQUE

Posted on • Updated on

131. Palindrome Partitioning

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;
}
}
``````