Scala algorithm: Find the longest palindrome within a string
Published
Algorithm goal
The palindrome in String XYZdZeXdZdZdX
is XdZdZdX. Compute the longest sub-string palindrome in a given string.
Note: there are many solutions to this problem that may be wrong.
Test cases in Scala
Algorithm in Scala
43 lines of Scala (compatible versions 2.13 & 3.0).
Explanation
We use a dynamic programming style solution.
Notice that if 'aBa' is a palindrome, then '?aBa!' is also a palindrome if '?' and '!' are equal. (this is © from www.scala-algorithms.com)
By defining Palindrome(i, j) to be 'true' if there is a palindrome starting at i, and ending at j, we have the following:
- Palindrome(i, i) = true
- Palindrome(i, i + 1) = char at i == char at i + 1
- Palindrome(i, j) = Palindrome (i + 1, j - 1) && char at i == char at i + 1
Scala concepts & Hints
Drop, Take, dropRight, takeRight
Scala's `drop` and `take` methods typically remove or select `n` items from a collection.
For-comprehension
The for-comprehension is highly important syntatic enhancement in functional programming languages.
Range
The
(1 to n)
syntax produces a "Range" which is a representation of a sequence of numbers.