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

    }
  }
}

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
};

Blog

Kipack Jeong

Leetcode

Join Our Newsletter. No Spam, Only the good stuff.

Related