Grokking Dynamic Programming Patterns for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Peng Xu
wrong result when s1="passport" and s2 = "ppsspt"

Peng Xu

Dec 18, 2023

For below test case when s1="passport" and s2 = "ppsspt"

I got result 1 for the longest common substring. Seems the solution might not be correct. could you help to check?

class Solution:   def findLCSLength(self, s1, s2):     # TODO: Write your code here     # index 1 and 2     def helper(i1, i2, count):       if i1 == len(s1) or i2 == len(s2):         return count             if s1[i1] == s2[i2]:         return helper(i1+1, i2 + 1, count + 1)       else:         c1 = helper(i1, i2 +1, 0)         c2 = helper(i1+1, i2, 0)         c3 = helper(i1 + 1, i2 + 1, 0)         return max(c1, c2, c3)     return helper(0,0, 0)

0

0

Comments
Comments
Peng Xu
Peng Xu2 years ago

found the issue myself, the 2nd last line should be:

return max(count, c1, c2, c3)

Shubham Ghule
Shubham Ghule2 months ago

c3 is also processed as part of c1 or c2. c3 is redundant

On this page

Problem Statement

Try it yourself