Start learning free

LESSON 173 OF 338 · STRINGS

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


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 2
    Ctrl + Enter to check

    GO · STRINGS

    Palindrome Check in Go, explained

    Problem overview

    The function isPalindrome receives a string, input, and returns true when it reads the same forwards and backwards. The input "madam racecar madam" gives true, because reversing it gives the same text, and "abcbx" gives false. Spaces count as characters, and so does letter case: "Madam" is not a palindrome here, since reversed it starts with a lowercase m.

    Approach: reuse a reversal

    There are two natural ways to solve this. The statement's hints describe the two-pointer method: one index from the left, one from the right, moving toward each other and comparing characters. It needs only O(1) extra space.

    This lesson takes a shorter path that is easier to write. A palindrome is a string equal to its own reversal, so reverse the input and compare the two. The lesson supplies a helper, reverseString, that returns its argument reversed, and the function calls it without defining it. The price is memory: the reversed copy takes O(n) extra space, so this version doesn't meet the O(1) space target the statement mentions. The time is still O(n).

    For comparison, the two-pointer version needs no helper and no copy:

    func isPalindrome(input string) bool {
    for i, j := 0, len(input)-1; i < j; i, j = i+1, j-1 {
        if input[i] != input[j] {
            return false
        }
    }
    return true
}

    It stops at the first mismatched pair and never looks at a pair twice, so it also runs in O(n) time. It compares bytes, which is fine for ASCII text. The lesson's own solution, shown below, is the shorter one. Both give the same answers on ASCII input such as the two examples.

    Step by step

    1. Call reverseString(input) and keep the result in reversedInput, declared with :=.
    2. Return the comparison input == reversedInput. In Go, == on two strings compares their contents, and the comparison is itself a boolean, so it can be returned directly without an if.

    The solution in Go

    func isPalindrome(input string) bool {
    reversedInput := reverseString(input)
    return input == reversedInput
}

    Language details worth knowing

    Go compares strings by value, so no special method is needed. Two different string variables with the same text are equal. The comparison stops at the first difference, so it takes O(n) time in the worst case.

    Writing if input == reversedInput { return true } else { return false } works, but it only repeats what the expression already says. Returning the boolean expression is the usual Go style.

    Which characters the check treats as units depends on how the helper reverses. A helper that reverses runes gives the expected answer for text with accents. A helper that reverses raw bytes would report a palindrome such as "éé" as false, because the two bytes of each é swap places. For ASCII input, the two kinds of helper agree.

    Complexity

    Time is O(n): the reversal is one pass, and the comparison is another. Space is O(n) for the reversed copy.

    Edge cases and common mistakes

    • The empty string and any single character are palindromes, and the code returns true for both.
    • Case and spaces are significant. "Madam" returns false, and so does "race car": reversed, it reads "rac ecar".
    • Comparing the string with itself instead of with the reversed value (input == input) always gives true.
    • If you define the helper yourself, make sure it returns a new string. Go strings can't be modified in place, so nothing the helper does can change input.

    Testing

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