最长公共子序列我的无限循环在哪里？

Question

我试图在Ruby中实现最长的通用子序列算法，但我得到的堆栈级别太深了。我知道这可能意味着我有一个无限循环，但我无法发现它。下面是我最好的尝试，我哪里做错了？

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

n、 我试图返回子序列本身，而不是其长度。

Answer 1

使用示例字符串尝试一下：abcd和bc并逐步完成它。

你会发现这两条线有问题：

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

因为'abcd'[0...-1]-

它应该是[0..2]。

此外，如果string1，则可以使用。chars。没有一个{| x | string2。包括？（x）}以替换if！（string1.chars.any？{x | string2.include？（x）}）