Start learning free

LESSON 200 OF 414 · STRINGS

Palindrome Check in Scala: Compare a String with Its Reverse

Practice O(n) Read the full explanation

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 (the two-pointer approach below achieves this).


Hints:

For the string to be a palindrome, for each character, there is a corresponding element which should be equal to that one:
  • the character at index 0 equals the character at index n - 1
  • the character at index 1 equals the character at index n - 2
  • the character at index 2 equals the character at index 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 through the algorithm?

For as long as i < j:
  • 1. We should check if the characters at indices i and j are different, 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 2
    Ctrl + Enter to check

    SCALA · STRINGS

    Palindrome Check in Scala, explained

    Problem overview

    The method isPalindrome receives a String named input and returns a Boolean: true if the text reads the same backward as forward, false otherwise. Every character counts, including spaces, so "madam racecar madam" is a palindrome (its reverse is the same string) and "abcbx" is not.

    Approach: reverse, then compare

    A string is a palindrome exactly when it equals its own reverse. That turns the problem into two operations: build the reversed string, then compare it with the original. Scala has both built in: reverse on a string returns a new reversed string, and == compares two strings by their contents.

    This is the shortest solution and the easiest to see is correct. It has a cost: the reversed copy takes O(n) extra space, where n is the length of the string. The task statement asks for O(1) extra space, which a two-pointer check meets. That approach compares the first and last characters, then the second and second-to-last, moving inward until the pointers meet, and never builds a copy. This lesson focuses on the version that leans on the standard library.

    Step by step

    1. Reverse the input. Store input.reverse in a val named reversedInput. The call takes no parentheses and returns a new string. The original is untouched, because strings can't be modified.
    2. Compare and return. Make input == reversedInput the last line of the method. Scala returns the value of the last expression, so no return is needed, and since a comparison is already a Boolean, there is no need for an if that returns true or false by hand.

    The solution in Scala

    class Solution {
    def isPalindrome(input: String): Boolean = {
        val reversedInput = input.reverse
        input == reversedInput
    }
}

    The Scala details worth knowing:

    • == compares contents. In Scala, == on strings checks whether they hold the same characters, even if they are two separate objects. That differs from Java, where == on objects compares references. For a reference comparison, Scala has eq.
    • The last expression is the result. The block ends with input == reversedInput, with no semicolon and no return. If you added a statement after it, the method would return that instead.
    • reverse comes from Scala's collection methods. A String behaves like a sequence of characters, and reverse gives back a String.
    • Case and spaces matter. The comparison is exact: "Aba" is not a palindrome, because 'A' and 'a' are different characters, and a phrase like "A man a plan" is judged with its spaces included.

    Complexity

    Time: O(n). Reversing visits each character once, and the comparison looks at up to n characters. Both are linear, so the total is O(n).

    Space: O(n). The reversed string is a second copy of the input. Because of that copy, this solution does not reach the O(1) extra space of the two-pointer check.

    A two-pointer version

    For comparison, this version meets the O(1) space target:

    def isPalindrome(input: String): Boolean = {
    var i = 0
    var j = input.length - 1
    while (i < j) {
        if (input(i) != input(j)) return false
        i += 1
        j -= 1
    }
    true
}

    It stops as soon as one pair of characters differs, so it can finish early, and it allocates no new string. When i reaches j, every pair matched.

    Edge cases and common mistakes

    • Empty string. It equals its own reverse, so the result is true.
    • One character. Always a palindrome.
    • Two different characters. "ab" reverses to "ba", so the result is false.
    • Even and odd lengths. "abba" and "abcba" both work with no special handling, since the whole string is compared.
    • Upper and lower case. "Aba" returns false. To ignore case, convert first with toLowerCase, but only if the task says to.
    • Calling reverse() with parentheses. This does not compile for the string method, so write input.reverse.

    Testing

    • "madam racecar madam" gives true.
    • "abcbx" gives false.
    • "" gives true.
    • "ab" gives false, and "aa" gives true.
    • "abcba" gives true.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free