Data Structures

Validate Palindrome

Given a string s, return whether the string is a palindrome.

A "palindrome" is a string that's the same forwards and backwards.

Example:

s = "racecar"=> returns True \notag \begin{align*} &\texttt{s = "racecar"} \\ & \texttt{=> returns True } \end{align*}

Explanation: "racecar" reads the same way forwards and backwards.

First Few Test Cases:

A string is a palindrome if the 1st and last characters are equal, and the 2nd and 2nd-to-last characters are equal, and so on.

To solve this problem, you need to remember that Python treats strings like arrays - strings have a 0th character, a 1st character, and so on. You can get the 0th character by writing s[0]\texttt{s[0]}. Here's a picture of this:

image

This means we can check if our string is a palindrome by starting at both ends of the string and moving inwards, making sure both characters are the same. We'll return False if the two current characters don't match, and True if all the characters matched.

Time Complexity O(n)O(n), where n is the size of the array. This is because we loop through every element in the array, so we have to do O(n)O(n) operations.

Space Complexity O(1)O(1). We only have to store 2 variables left and right. No matter how big our array gets, we always use the same amount of memory, which means the amount of memory needed doesn't grow at all as our input gets big. This is O(1)O(1).

Mark as Completed:
Submits:
isValid
Test your code to get an output here!
isValid(
)
Test your code to get an output here!