CODEWITHSUNDEEP
rubyalgorithmsubsequence
achalk
achalk

Reputation: 3459

Longest common subsequence—where is my infinite loop?

I'm trying to implement the longest common subsequence algorithm in Ruby, but I'm getting the stack level too deep error message. I know this probably means I have an infinite loop, but I cannot spot it. Below is my best attempt—where am I going wrong? 

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.b. I'm trying to return the subsequence itself, not its length.

Upvotes: 0

Views: 353

Answers (1)

Ho Man
Ho Man

Reputation: 2345

Try it with a sample string: abcd and bc and step through it.

You'll realise that these two lines have issues:

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

Because 'abcd'[0..-1] -> 'abcd' so the moment it reaches x = ... line it'll get stuck.

It should be [0..-2] instead.

Also, you can use if string1.chars.none? { |x| string2.include?(x)} to replace if !(string1.chars.any? { |x| string2.include?(x)})

Upvotes: 3

Related Questions