Compare from both ends
Check whether a string reads the same both ways. About 7 minutes.
Words that read the same both ways
"Racecar", "madam", "noon": palindromes read the same forwards and backwards. To check one, compare the first character with the last, the second with the second-last, and so on, working inwards.
You already know this move: it's two fingers walking towards each other, like reversing an array in place. The only difference is that you compare instead of swap.
First and last: 'r' and 'r'. They match, so step both inward.
Stop at the middle, or at the first mismatch
Keep going while the left finger is before the right one. If the string has an odd length, the fingers meet on the middle character, which has nothing to match and doesn't need to.
The moment a pair differs, you know the answer is no, so stop there. And you never had to build a reversed copy of the string to compare against.
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return TrueChecking "rotor", which characters get compared with each other?
- Ar with r, then o with o
- BEvery character with every other
- CEach character with the next one
Show the answer
r with r, then o with o. First with last, then second with second-last. The middle t has no partner, so the check stops.
Palindrome check
Return true if s reads the same from left to right as from right to left, and false otherwise. Every character counts, including spaces. The empty string counts as a palindrome.
s = "racecar" → true
0 ≤ length of s ≤ 10,000 · s has lowercase letters and spaces