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?