Same both ways
Walk a list by passing positions down the calls, not by copying it. About 10 minutes.
Pass positions, not smaller lists
In the last step, each call got a shorter copy of the string. For lists there is a cheaper way: keep the whole list and pass along the positions that the call should work on, like putting two bookmarks in the same book.
The function the problem asks for can't take extra positions, so write a small helper that does, and have the main function call it once with the starting positions.
check(0, 4): 3 and 3 match. Ask check(1, 3) about the inside.
Compare the ends, then go inward
A list reads the same both ways if its first and last values match and the part between them also reads the same both ways. That inner part is the same question, one step in from each end.
If the ends don't match, you already know the answer is no: no need to call again.
def check(nums, left, right):
if left >= right:
return True
if nums[left] != nums[right]:
return False
return check(nums, left + 1, right - 1)
def is_palindrome(nums):
return check(nums, 0, len(nums) - 1)Checking [4, 1, 6, 1, 7], what does check(nums, 0, 4) do?
- AReturns false at once
- BCalls check(nums, 1, 3)
- CReturns true, because the middle 1, 6, 1 matches
Show the answer
Returns false at once. 4 and 7 don't match, so the list can't read the same both ways. No smaller call is needed.
Same both ways
Return true if nums reads the same from left to right as from right to left, and false otherwise. Use recursion with a helper that takes the two positions being compared.
nums = [3, 8, 5, 8, 3] → true
0 ≤ n ≤ 1,000 · −1,000,000,000 ≤ each value ≤ 1,000,000,000 · about n ÷ 2 calls deep