You get a string s of lowercase letters. Return true if s is a palindrome, and false if it is not.
A palindrome stays the same when you read it backwards. An empty string counts as a palindrome.
Solve it with a recursive function. A loop would work too, but this lesson practices recursion.
Example 1:
Input: s = "rotator" Output: true Explanation: Backwards, it is still "rotator". The pairs r-r, o-o and t-t match. The a in the middle has no partner.
Example 2:
Input: s = "reader" Output: false Explanation: Backwards, it is "redaer". The outer pairs r-r and e-e match. The middle pair is a and d, and they differ.
Example 3:
Input: s = "redder" Output: true Explanation: The pairs r-r, e-e and d-d match. No letter is left over in the middle.
Constraints:
shas 0 to 1,000 letters.- Each letter is a lowercase English letter, from a to z.
Your solution should run in O(n) time, where n is the length of s.
Hints:
Look at the first and the last letter. If they differ,
s is not a palindrome. If they match, what is left to check?
Write a helper that checks the letters between two positions, lo and hi. It compares the letters at lo and hi. If they match, it calls itself with lo + 1 and hi - 1. It stops when lo reaches or passes hi.
Each call compares one pair and moves both ends inward. That makes about n / 2 calls: O(n) time.
The calls wait for each other, so up to n / 2 of them are open at once: O(n) extra space.
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check
