我试图在ruby中实现最长的公共子序列算法,但是我得到了stack level too deep错误消息。我知道这可能意味着我有一个无限循环,但我无法发现它下面是我最好的尝试,我哪里做错了?

def lcs(string1, string2)
  if !(string1.chars.any? { |x| string2.include?(x)})
    return ""
  elsif string1[-1] == string2[-1]
    return lcs(string1[0..-2], string2[0..-2]) + string1[-1]
  else
    x = lcs(string1, string2[0..-1])
    y = lcs(string1[0..-1], string2)
    x.length > y.length ? x : y
  end
end

注意,我试图返回子序列本身,而不是它的长度。

最佳答案

尝试使用一个示例字符串:abcdbc并单步执行。
你会发现这两条线有问题:

x = lcs(string1, string2[0..-1])
y = lcs(string1[0..-1], string2)

因为一旦它到达线就会卡住。
应该改为'abcd'[0..-1] -> 'abcd'
此外,您还可以使用x = ...
替换[0..-2]

关于ruby - 最长的公共(public)子序列-我的无限循环在哪里?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/43130816/

10-13 02:50