Start learning free

LESSON 201 OF 415 · STRINGS

Palindrome Check in Swift: 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

    SWIFT · STRINGS

    Palindrome Check in Swift, explained

    Problem overview

    The method isPalindrome(_ input: String) -> Bool returns true when the string reads the same forwards and backwards. "madam racecar madam" is a palindrome, because reversing it, spaces included, gives the same text. "abcbx" is not, because its reverse is "xbcba".

    The comparison is exact. Spaces count as characters, and uppercase and lowercase letters differ, so "Aa" is not a palindrome.

    Approach: reverse, then compare

    A palindrome equals its own reverse. That gives a very short solution: build the reversed string and test whether it is equal to the original. The comparison is a single expression, so there is no loop to write and no index to get wrong.

    The statement's hints describe another approach, two pointers that start at both ends and move toward the middle, comparing one pair of characters at a time. It can stop at the first mismatch, so it compares fewer characters on strings that fail early. This lesson takes the shorter route with the reversal. Both approaches look at every character in the worst case, so both are linear in time, but the reversal builds a second string, which costs O(n) extra space. The two-pointer version is the one that fits the O(1) space note.

    Step by step

    1. Reverse the input. Declare the constant reversedInput as String(input.reversed()). The call reversed() returns the characters in reverse order, but as a collection and not as a String, so it is wrapped in String(...).
    2. Compare and return. input == reversedInput already evaluates to true or false, so the method returns it directly, with no if.

    The solution in Swift

    class Solution {
    func isPalindrome(_ input: String) -> Bool {
        let reversedInput = String(input.reversed())
        return input == reversedInput
    }
}

    The Swift details worth a closer look:

    • What reversed() returns. On a string it gives a ReversedCollection<String>, a lightweight view that walks the characters from the end. Passing it to String(...) copies those characters into a real string. That copy is the O(n) extra space.
    • Comparison by contents. == on two strings compares their characters, not where they are stored. Swift also treats strings as equal when they are canonically equivalent, so "\u{E9}" (a single "é") equals "e\u{301}" ("e" plus a combining accent).
    • Characters, not bytes. The reversal works on Character values. A letter with a combining accent stays in one piece, so a string such as "e\u{301}e\u{301}" is correctly judged a palindrome.
    • Returning a comparison. Writing if input == reversedInput { return true } else { return false } works but only repeats what the expression already says.

    Complexity

    Time: O(n). Reversing visits each character once, and the comparison does at most n character checks.

    Space: O(n). The reversed string is a second copy of the input. The note in the statement asks for O(1), which the two-pointer version reaches by working on the original string, or on an array of its characters, in place.

    Edge cases and common mistakes

    • Empty string. Its reverse is also empty, so the result is true.
    • One character. "a" is a palindrome.
    • Case. "Aa" returns false, because "A" and "a" are different characters. If a problem wants a case-insensitive answer, lowercase the input first with lowercased().
    • Spaces and punctuation. "A man" returns false. Nothing is skipped; every character takes part in the comparison.
    • Forgetting String(...). input == input.reversed() does not compile: the compiler cannot apply == to a String and an array of characters, because reversed() gives characters, not a String.
    • Even and odd lengths. "abba" and "aba" both work with no special handling, which a two-pointer loop also gives you with the condition i < j.

    Testing

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