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!

Blog Archive