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)