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:
Right :). But I'm sure that the person who have put it on Stack over flown has done it after many iterations!
Post a Comment