回文分区ruby无输出

Question

您好，我正在使用递归解决回文分割问题。此问题是 return 给定字符串输入的所有可能的回文分区。

输入："aab"
输出：[["aa", "b"], ["a", "a", "b"]]

回文分区定义：给定一个字符串S，一个分区是一组子串，每个子串包含一个或多个字符，这样每个子串都是一个回文

我的代码如下。我遇到的问题是结果数组永远不会被正确填充。从高层次上看，我觉得我的逻辑是有道理的，但是当我尝试调试它时，我不太确定发生了什么。

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

是的，您确实想使用递归。我没有仔细分析你的代码，但我看到一个问题是方法 dfs:

中的以下内容

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

如果 if 条件满足，return 不带参数将 return nil。也许你想要 return result.

这里是一个相对紧凑的，类似Ruby的写法。

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

理解此递归如何工作的最佳方法是添加一些 puts 语句并重新运行它。

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

回文分区ruby无输出

palindrome partition ruby no output

ruby

palindrome