Categories
Kotlin

Kotlin Palindrome Checker

This post, based on code from my new Kotlin Cookbook, shows how to write a palindrome checker in Kotlin. Along the way it discusses raw strings and regular expressions, writing functions as single statements, and creating an extension function on String.

First, a quick definition. A palindrome is a string whose characters are the same forwards and backwards, ignoring case and with punctuation removed. Here are a few palindromes, which can serve as test cases later:

  • racecar
  • Madam, in Eden, I’m Adam.
  • Flee to me, remote elf!
  • Sex at noon taxes.
  • A Santa pets rats, as Pat taps a star step at NASA.

Make of them what you will. 🙂

To make a palindrome checker, you need to remove case sensitivity and replace all the punctuation with empty strings. The first task is trivial: just use the String functions toLowerCase or toUpperCase, whichever you prefer.

To handle regular expressions, Kotlin has a few mechanisms, but one is to use a raw string with the regex in it and then invoke the toRegex function on it.

In the case of a palindrome, a decent regex would be """[\W+]""". The square brackets represent a choice. The expression is a predefined character class \W, meaning the opposite of \w, where the lowercase version represents any word character. Word characters are lowercase a-z, uppercase A-Z, the numbers 0-9, and an underscore, _. Therefore \W represents all non-word characters, which can be used to get rid of all punctuation (other than underscores, but if that’s important, that can always be added later). The plus sign means one or more, so the overall effect is to look for one or more non-word characters. Since this post (and the book) is written for the JVM version of Kotlin, you can see the JavaDocs for java.util.regex.Pattern class for details.

The triple quotes surrounding the regex represent a “raw” string in Kotlin, so you don’t have to escape the backslash on the W when writing a regular expression. Raw strings can be written over several lines, too, but that’s not necessary here. To make the raw string into a regular expression, invoke the toRegex function on it.

"""[\W+]""".toRegex()

The tricky “replace” function

To use the regular expression, String has a function called replace, but it’s a bit tricky. There are two overloaded versions of replace, one whose first argument is a string and one whose first argument is a regex. The signatures are:

// First arg is String, last arg has default value "false"
public fun String.replace(
    oldValue: String,
    newValue: String,
    ignoreCase: Boolean
): String

and

// First arg is a regular expression
public inline fun CharSequence.replace(
    regex: Regex,
    replacement: String
): String

For the first version of replace, the library implementation shows that the ignoreCase parameter has a default value of false, so invoking the function without that parameter is legal. That, unfortunately, makes it easy to confuse with the second version, as the following test case shows.

@Test
fun `demonstrate replace with a string vs regex`() {
    assertAll(
        { assertEquals("one*two*", "one.two.".replace(".", "*")) },
        { assertEquals("********", 
              "one.two.".replace(".".toRegex(), "*")) }
    )
}

The first assertion replaces the single dots in “one.two.” with a single star, *, because it’s using the version of replace that takes a string as the first argument. That means it looks for literal dots in the string and replaces them with a star.

The second assertion uses the version of replace that takes a regular expression as the first argument. In regular expressions, a single dot represents any single character, so the result is to replace all the letters in “one.two.” with stars, as shown.

I should mention that I didn’t come up with that example on my own. I saw it in a slide found here, which is one of the presentations, hosted at SpeakerDeck, provided by the Kotlin core team members. The slides are a little dated, but still useful. You can find all of them linked from this GitHub repository.

isPalindrome Function

Returning to the palindrome checker, version 1 is shown as a function called isPalindrome that takes a string argument and returns a boolean:

fun isPalindrome(string: String): Boolean {
    val testString = string.toLowerCase()
        .replace("""[\W+]""".toRegex(), "")
    return testString == testString.reversed()
}

This works by converting the supplied string to lower case, then using the replace function with the needed regex, and then using == to see if it is equivalent to its reverse. It’s notable that in Kotlin String has a reverse function, and that operator overloading means that the == sign invokes the equals function.

While this works, it’s arguably not idiomatic. Kotlin favors single statement functions, where you can just assign a statement implementation to the function signature. The hard part in this particular function is that it is currently two statements — one to create the test string, and one to do the equality check. This is where the convenient scope function called let comes in, as you can see in version 2 of the palindrome function:

fun isPalindrome(string: String) =
    string.toLowerCase()
          .replace("""[\W+]""".toRegex(), "")
          .let { it == it.reversed() }

The replace function returns the new string, so you can chain another function call to it. Then, according to the documentation, the let function “calls the specified function block with this value as its argument and returns its result”. The provided block is a lambda with a single argument, referred to as it, and returns the last evaluated expression, which is the boolean that results from the equivalence check.

To really bring this home, this top-level function seems to be a natural extension function on the String class (or CharSequence interface) , so here is the final version of the function:

fun String.isPalindrome() =
    this.toLowerCase()
        .replace("""[\W+]""".toRegex(), "")
        .let { it == it.reversed() }

Inside the extension function, the current instance is referenced as this, but the rest of the implementation is the same.

Finally, here are a couple of tests to demonstrate that the function works correctly:

@Test
fun `these are palindromes`() {
    assertAll(
        { assertTrue("Madam, in Eden, I'm Adam".isPalindrome()) },
        { assertTrue("Flee to me, remote elf!".isPalindrome()) },
        { assertTrue("Sex at noon taxes".isPalindrome()) },
        { assertTrue("A Santa pets rats, as Pat taps a star step at NASA".isPalindrome()) }
    )
}

@Test
fun `check isPalindrome is not just returning true`() {
    assertFalse("this is not a palindrome.isPalindrome())
}

The result is a simple function that can be used for any string, and the implementation shows how to use replace, reverse, regular expressions, the let function, and how to implement a simple extension function.

As usual, the source code can be found in the GitHub repository for my Kotlin Cookbook. The tests there include one for the massive 543-word palindrome, written as a multi-line string, from the Gigantic List of Palindromes. Just being able to verify that palindrome was entertaining enough to do this entire exercise. 🙂