Shail Patel - 2 years ago 83
Ruby Question

# palindrome partition ruby no output

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

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"]]
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download