迴文分區紅寶石沒有輸出

Question

嗨我正在使用遞歸回文分區問題。此問題將返回給定字符串輸入的所有可能的迴文分區。

輸入： 「AAB」
輸出：[[ 「AA」， 「B」]，[ 「一」， 「一個」， 「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不帶參數將返回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"]]