0

I try to implement the Longest Common Subsequence problem that it can be found in various online programming challenges. the piece of code is 

sub=""

def lcs(x, y):
  sub2=sub1=''
  global sub
  if len(x) == 0 or len(y) == 0:
      return sub
  if len(x) != 0 and len(y) != 0:
      sub1 = [i for i in x][-1]
      sub2 = [i for i in y][-1]

      if sub1!=sub2:
          if len(x) > len(y):
              x=x[:-1]
          elif len(x) < len(y):
              y=y[:-1]
          else:
              x=x[:-1]
              y=y[:-1]
      else:
          sub=sub+sub1
          x=x[:-1]
          y=y[:-1]

      lcs(x, y)

print lcs('a','a')

i expect the print statement to return 'a' but instead returns None. I think the problem is that the steps of the recursion saves the previous output and when the print is called it reaches these previous results. what am i doing wrong and how should i handle such cases?

b10n1k
  • 567
  • 5
  • 21
  • 4
    You have to return the result of the recursive call. `return lcs(x, y)`. – g.d.d.c Nov 22 '18 at 17:03
  • Note, the second duplicate target was literally the first result I got when I copy-and-pasted your title into a google search. Please try to at least try to find if someone has asked a similar question before you post a new one. I understand sometimes its difficult to articulate if you don't know what is wrong, but again, just googling your title brought me to one... – juanpa.arrivillaga Nov 22 '18 at 17:07

0 Answers0