palindromeパーティションルビ出力なし

Question

こんにちは私は再帰を使用して回文パーティションの問題をやっています。この問題は、指定された文字列入力の可能なすべてのパリンドロームパーティションを返します。

入力： "AAB"
出力：[[ "AA"、 "B"]、[ "A"、 "A"、 "B"]]

パリンドロームパーティション定義：ストリングS所与パーティションは、各部分文字列が回文文字列であるように、それぞれが1つ以上の文字を含む部分文字列のセットです。

私のコードは以下の通りです。私が抱えている問題は、結果の配列が決して正確に入力されないということです。高レベルから私の論理が理にかなっているように感じますが、デバッグしようとすると何が起こっているのか分かりません。

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条件が満たされた場合

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

、引数なし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"]]