## Leetcode

**Palindrome Partitioning**

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of

A palindrome string is a string that reads the same backward as forward.

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.

**Depth first search approach**

- dfs the possible set of letters starting from index 0.
so like in s = "aaba", start from
`s[0] = "a"`

, possible forms would be :`a`

,`aa`

,`aab`

,`aaba`

Among above candidates, if candidate is not a palindrome we would skip to next candidate.

```
function dfs(s, start, subList, result){
for(var end = start ; end < s.length; end ++){
if(isPalindrome(start, end)){
}
}
}
```

If candidate is palindrome, add the current candidate to `subList`

, then dfs in after the next following letter after the candidate.

```
function dfs(s, start, subList, result){
for(var end = start ; end < s.length; end ++){
if(isPalindrome(start, end)){
subList.push(s.slice(start, end+1)
dfs(end+1, subList, result)
}
}
}
```

Setup the base condition of this dfs recursive call. Which would be when `start >= s.length`

, then add `subList`

to result then get out from single recursion. Then backtrack by popping out an element from subList.

```
function dfs(s, start, subList, result){
if(start >= s.length){
result.push([...subList])
return
}
for(var end = start ; end < s.length; end ++){
if(isPalindrome(start, end)){
subList.push(s.slice(start, end+1)
dfs(end+1, subList, result)
subList.pop() // backtracking
}
}
```

Now the whole setup would look like this.

```
var answer = function(s) {
const result = []
function isPalindrome(s, start, end){
while(start < end){
if( s[start] !== s[end]){
return false;
}
start ++
end --
}
return true;
}
function dfs(s, start, subList, result){
if(start >= s.length){
result.push([...subList])
return
}
for(var end = start; end < s.length; end++){
if(isPalindrome(s,start,end)){
subList.push(s.slice(start,end+1))
dfs(s,end+1, subList, result)
subList.pop()
}
}
}
dfs(s, 0, [], result)
return result
};
```

## Top comments (0)