LESSON 228 OF 348 · TWO POINTERS

Palindrome Check in Rust

Practice O(n)

Given a string, determine if it is a palindrome.

A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward

Example 1:

Input:  "madam racecar madam"

Output: true

Example 2:

Input:  "abcbx"

Output: false

Note:

Your algorithm should run in O(n) time and use O(1) extra space.

Hints:

For the string to be a palindrome, for each character, there is a corresponding element which should be equal to that one:

s[0] == s[n - 1]
s[1] == s[n - 2]
s[2] == s[n - 3]
...

How can we check all these pairs of corresponding characters while traversing the string one time?

We can use two pointers! One index variable i starting from the beginning (i = 0) and one index variable j starting from the end of the string (j = n - 1). How should we move these pointers throught the algorithm?

For as long as i < j:

1. We should check if s[i] != s[j] and if so, we conclude the string is not a palindrome and return false.
2. Move i one step to the right.
3. Move j one step to the left.
4. Go to step 1.

If i became greater than or equal to j and we haven't returned false, then we can conclude the string is a palindrome and return true.

STEP 1 OF 9

Guided

Ctrl + Enter to check