Our checkReverse method does the job and the nice thing is that the implementation is very simple. As hinted earlier, at some point, though, we might want to exchange the implementation for a better version. One problem of the naive reverse approach is that for every string we check, we need twice the memory to perform the actual equality check. With growing adoption of our palindrome-checking-service however, users want to have larger and larger strings checked for palindromicity, reaching millions of chars in length! When we want to check such a large string, it is unthinkable to just allocate twice the memory, certainly we can do better than that!
After a quick round on the white board, we come up with an alternative way to check for palindromicity: we keep track of two indices, starting from the very left and the very right of the palindrome. The idea is to then work our way towards the middle, comparing the characters as we go:
We start with an implementation and on the first try, we come up with this:
def checkIndices(s: String): Boolean = {
@tailrec
def loop(i: Int, j: Int): Boolean = (i,j) match {
case (i,j) if i == j => true
case (i,j) if s(i) != s(j) => false
case (i,j) if s(i) == s(j) => loop(i+1,j-1)
}
loop(0,s.length-1)
}
To test this, we need a property. As we are pretty sure that checkReverse is a correct implementation, why not use that as reference:
property("checkIndices") = forAll(maybePalindrome) { s =>
checkReverse(s) == checkIndices(s)
}
We say that for all strings generated by maybePalindrome, our checkIndices method should return the same result as checkReverse. We define maybePalindrome as:
val maybePalindrome: Gen[String] = Gen.oneOf(palindromeGen,arbitrary[String])
Note the use the oneOf method from Gen to create a generator that will sometimes produce palindromes and sometimes arbitrary strings. Now let’s test our new palindrome checker:
> test
[info] ! Palindrome.checkIndices: Exception raised on property evaluation.
[info] > ARG_0: ""
[info] > Exception: java.lang.StringIndexOutOfBoundsException:
String index out of range: 0
We forgot about the empty string! Okay that’s easy, let’s fix that and just run the tests again:
> test
[info] ! Palindrome.checkIndices2: Exception raised on property evaluation.
[info] > ARG_0: ""
[info] > Exception: java.lang.StringIndexOutOfBoundsException:
String index out of range: 2
Another error, this time when handling palindromes with an even number of chars. Investigating this, we come to the conclusion, that we forgot to consider what happens when the two indices never meet because they pass each other, due to an even number of chars:
Here in the next step, our current algorithm would continue with i and j in swapped position and then continue both indexes until we run out of chars, leading to the StringIndexOutOfBoundsException from above. To fix this, we add another case to our implementation:
def checkIndices(s: String): Boolean = {
@tailrec
def loop(i: Int, j: Int): Boolean = (i,j) match {
// additional case: check for adjacent indices
case (i,j) if i+1 == j => s(i) == s(j)
case (i,j) if i == j => true
case (i,j) if s(i) != s(j) => false
case (i,j) if s(i) == s(j) => loop(i+1,j-1)
}
// additional check: "" is a palindrome
s.isEmpty || loop(0,s.length-1)
}
Feeling lucky, we run our tests again:
> test
[info] + Palindrome.checkReverse: OK, passed 100 tests.
[info] + Palindrome.checkIndices: OK, passed 100 tests.
[info] Passed: Total 2, Failed 0, Errors 0, Passed 2
Success! For 100 randomly generated strings, our implementation of checkIndices returned the same result as our reference implementation checkReverse.
