# Dev note 8JAN2021

## 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 = "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
};
``````