DEV Community

Kipack Jeong
Kipack Jeong

Posted on

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[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)){

    }
  }
}

Enter fullscreen mode Exit fullscreen mode

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)
    }
  }
}
Enter fullscreen mode Exit fullscreen mode

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
    }
}
Enter fullscreen mode Exit fullscreen mode

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
};
Enter fullscreen mode Exit fullscreen mode

Top comments (0)