Problems178
Search for a command to run...
Initialization
From the current index, try every possible end for the next piece. If that piece reads the same forwards and backwards, take it and partition the rest; otherwise reject it immediately, which prunes the whole subtree below it.
Backtracking
1function partition(s) {2 const res = [];3 const path = [];//s: aab4 dfs(0, s, path, res);5 return res;6}7 8function dfs(index, s, path, res) {9 // Base case: the whole string is consumed10 if (index === s.length) {11 res.push([...path]);12 return;13 }14 15 // Try every end point for the next piece16 for (let i = index; i < s.length; ++i) {17 if (isPalindrome(s, index, i)) {18 path.push(s.substring(index, i + 1));19 dfs(i + 1, s, path, res);20 path.pop();21 }22 }23}24 25function isPalindrome(s, start, end) {26 while (start <= end) {27 if (s[start++] !== s[end--]) return false;28 }29 return true;30}