Friday, 4 July 2014

Palindromes in Scala... there is always a better way

What does one do while having dessert? Write some Scala code to find out the longest palindrome in a string. Some piece of code that makes you humble... :-) I came up with this (based on a double array in O(N^2))
```  def longestPalindrome(in: String): Option[String] = {
val inLength = in.length
val arr = Array.ofDim[Boolean](inLength, inLength)
for(i <- 0 until in.length) {
arr(i)(i) = true
if (i < inLength - 1 && in(i) == in(i+1)) arr(i)(i+1) = true
}

def helper(k: Int, i: Int, pal: Option[String]): Option[String] = {
val j = i + k - 1
if (in(i) == in(j)) {
arr(i)(j) = arr(i+1)(j-1)
if (arr(i)(j)) {
val npal = in.substring(i, j+1)
pal match {
case None => Some(npal)
case Some(s: String) => if (npal.size > s.size) Some(npal) else pal
}
} else pal
} else {
arr(i)(j) = false
pal
}
}

val allPals = for(k <- 3 to inLength; i <- 0 until inLength - k) yield helper(k, i, None)
val validPals = allPals.filter(o => o.isDefined).map(o => o.get)
if (validPals.isEmpty)
None
else
Some(validPals.maxBy(s => s.size))
}                                               //> longestPalindrome: (in: String)Option[String]

val str = "sdfsdfbbbgggbbggthierryjjyrreihtjdfdscdcdvdv"
//> str  : String = sdfsdfbbbgggbbggthierryjjyrreihtjdfdscdcdvdv
longestPalindrome(str)                          //> res0: Option[String] = Some(thierryjjyrreiht)

```
But then I found out on StackOverFlow, a much better way of doing this..... I was LOL when I saw this piece of code:
```  (for{i <- 2 to str.size; s <- str.sliding(i) if (s == s.reverse)} yield s).maxBy(s => s.size)
//> res1: String = thierryjjyrreiht
```
;-) There is always a better way

1 comment:

Hemant said...

Right :). But I'm sure that the person who have put it on Stack over flown has done it after many iterations!

• 4 years ago
• 5 years ago
• 2 years ago