Solving Maximum length of repeated subarray recursively

Viewed 38

I'm working on a naive recursive solution for the leetcode problem Maximum length of repeated subarray. The question is

Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays. Example 1: Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] Output: 3 Explanation: The repeated subarray with maximum length is [3,2,1].

Example 2: Input: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0] Output: 5

My code:

 def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        if not nums1 or not nums2:
            return 0
        if nums1[0] == nums2[0]:
            return 1 + self.findLength(nums1[1:], nums2[1:])
        else:
            return max(self.findLength(nums1[1:], nums2), self.findLength(nums1, nums2[1:]))

My code fails the test case [0,1,1,1,1] [1,0,1,0,1], returning 3 when the right answer is 2 ([0,1]). Intuitively I know this is because in the simulation

[0,1,1,1,1] 
 ^-------|
[1,0,1,0,1]      | -- match, max length +1
   ^         
______

[0,1,1,1,1] 
   ^----------|
[1,0,1,0,1]      | -- match, max length +1
     ^----------|

______

[0,1,1,1,1]
     ^-------------|
[1,0,1,0,1]      | -- mismatch, max length +0
       ^-------------|

______

[0,1,1,1,1]
       ^----------------|
[1,0,1,0,1]     | -- match, max length +1
         ^----------------|

I should not be adding +1 in the final "match" since it's not a subarray anymore. But how do I fix my code to take that case into account?

0 Answers
Related