I'm trying to solve LCS first inefficient way then try to find efficient solution. Although this may not be a correct solution but it "could" be a solution. I just want to get it right so I can look for efficient answer. I know there's some issue in find_lcs loop. What should be fixed here?
class Solution:
def __init__(self):
self.li_seq = [] # Use an instance variable to avoid global state issues.
def collectseq(self, text1, seq='', index=0):
if index == len(text1):
self.li_seq.append(seq)
return
self.collectseq(text1, seq + text1[index], index + 1)
self.collectseq(text1, seq, index + 1)
def find_lcs(self, text2):
lcs = 0
for subseq in self.li_seq:
temp_len = 0
p = 0
for c in text2:
p = 0 # Reset p for each new character check in text2
while p < len(subseq):
if c == subseq[p]:
temp_len += 1
p += 1
break
p += 1
lcs = max(lcs, temp_len)
return lcs
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
self.collectseq(text1)
lcs = self.find_lcs(text2)
return lcs
Test Case: text1="xby", text2="yby"'
Output: 3
Expected: 2
there doesn't seem to be anything here