palindrome partition ruby no output

Question

Hi I'm doing the palindrome partition problem using recursion. This problem is return all possible palindrome partitions of a given string input.

Input: "aab"
Output: [["aa", "b"], ["a", "a", "b"]]

A palindrome partition definition: given a string S, a partition is a set of substrings, each containing one or more characters, such that every substring is a palindrome

My code is below. The issue I'm having is that the result array never gets correctly populated. From a high level I feel like my logic makes sense, but when I try to debug it I'm not really sure what is going on.

def partition(string)
  result = []
  output = []
  dfs(string, 0, output, result)
  result
end

def dfs(string, start, output, result)
  if start == string.length
    result << output
    return
  end

  (start..string.length-1).to_a.each do |i|
    if is_palindrome(string, start, i)
      output << string[start..(i-start+1)]
      dfs(string, i+1, output, result)
      output.pop
    end
  end
end


def is_palindrome(string, start, end_value)
  result = true
  while start < end_value do
    result = false if string[start] != string[end_value]
    start += 1
    end_value -= 1
  end
  result
end

puts partition("aab")

Answer 1

Yes, you do want to use recursion. I haven't analyzed your code carefully, but I see one problem is the following in the method dfs:

if start == string.length
  result << output
  return
end

If the if condition is satisfied, return without an argument will return nil. Perhaps you want return result.

Here is a relatively compact, Ruby-like way of writing it.

def pps(str)
  return [[]] if str.empty?
  (1..str.size).each_with_object([]) do |i,a|
    s = str[0,i]
    next unless is_pal?(s)
    pps(str[i..-1]).each { |b| a << [s, *b] }
  end
end

def is_pal?(str)
  str == str.reverse
end

pps "aab"
  #=> [["a", "a", "b"],
  #    ["aa", "b"]]
pps "aabbaa"
  #=> [["a", "a", "b", "b", "a", "a"],
  #    ["a", "a", "b", "b", "aa"],
  #    ["a", "a", "bb", "a", "a"],
  #    ["a", "a", "bb", "aa"],
  #    ["a", "abba", "a"],
  #    ["aa", "b", "b", "a", "a"],
  #    ["aa", "b", "b", "aa"],
  #    ["aa", "bb", "a", "a"],
  #    ["aa", "bb", "aa"],
  #    ["aabbaa"]] 
pps "aabbbxaa"
  #=> [["a", "a", "b", "b", "b", "x", "a", "a"],
  #    ["a", "a", "b", "b", "b", "x", "aa"],
  #    ["a", "a", "b", "bb", "x", "a", "a"],
  #    ["a", "a", "b", "bb", "x", "aa"],
  #    ["a", "a", "bb", "b", "x", "a", "a"],
  #    ["a", "a", "bb", "b", "x", "aa"],
  #    ["a", "a", "bbb", "x", "a", "a"],
  #    ["a", "a", "bbb", "x", "aa"],
  #    ["aa", "b", "b", "b", "x", "a", "a"],
  #    ["aa", "b", "b", "b", "x", "aa"],
  #    ["aa", "b", "bb", "x", "a", "a"],
  #    ["aa", "b", "bb", "x", "aa"],
  #    ["aa", "bb", "b", "x", "a", "a"],
  #    ["aa", "bb", "b", "x", "aa"],
  #    ["aa", "bbb", "x", "a", "a"],
  #    ["aa", "bbb", "x", "aa"]] 
pps "abcdefghijklmnopqrstuvwxyz"
  #=> [["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m",
  #     "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]] 

The best way of understanding how this recursion works is add some puts statements and re-run it.

def pps(str)
  puts "\nstr=#{str}"
  return [[]] if str.empty?
  rv = (1..str.size).each_with_object([]) do |i,a|
    s = str[0,i]
    puts "i=#{i}, a=#{a}, s=#{s}, is_pal?(s)=#{is_pal?(s)}"
    next unless is_pal?(s)
    pps(str[i..-1]).each { |b| puts "b=#{b}, [s,*b]=#{[s,*b]}"; a << [s, *b] }
    puts "a after calling pps=#{a}"
  end
  puts "rv=#{rv}"
  rv
end

pps "aab"

str=aab
i=1, a=[], s=a, is_pal?(s)=true

str=ab
i=1, a=[], s=a, is_pal?(s)=true

str=b
i=1, a=[], s=b, is_pal?(s)=true

str=
b=[], [s,*b]=["b"]
a after calling pps=[["b"]]
rv=[["b"]]
b=["b"], [s,*b]=["a", "b"]
a after calling pps=[["a", "b"]]
i=2, a=[["a", "b"]], s=ab, is_pal?(s)=false
rv=[["a", "b"]]
b=["a", "b"], [s,*b]=["a", "a", "b"]
a after calling pps=[["a", "a", "b"]]
i=2, a=[["a", "a", "b"]], s=aa, is_pal?(s)=true

str=b
i=1, a=[], s=b, is_pal?(s)=true

str=
b=[], [s,*b]=["b"]
a after calling pps=[["b"]]
rv=[["b"]]
b=["b"], [s,*b]=["aa", "b"]
a after calling pps=[["a", "a", "b"], ["aa", "b"]]
i=3, a=[["a", "a", "b"], ["aa", "b"]], s=aab, is_pal?(s)=false
rv=[["a", "a", "b"], ["aa", "b"]]
  #=> [["a", "a", "b"], ["aa", "b"]]