LeetCode 5. Longest Palindromic Substring

LeetCode problem No.5.

No.4 is here.

modalsoul.hatenablog.com

5. Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Code 1

object Solution {
    def isPalindrome(s:String):Boolean = {
        val length = if(s.length%2 == 0) s.length/2 else s.length/2 + 1
        val left = s.take(length)
        val right = s.takeRight(length).reverseIterator
        !left.exists(_  != right.next)
    }
    def longestPalindrome(s: String): String = {
        for {
            len <- s.length to 1 by -1
            i <- 0 to s.length - len
        } {
            val tmp = s.drop(i).take(len)
            if(isPalindrome(tmp)) return tmp
        },
        s.take(1)
    }
}

Methods

• Get substring length from given string length by -1.
• Get substring starting index.
• Take substring.
• If substring is palindrome, this substring is answer.

Results

Runtime: 2384 ms Memory Usage: 51.1 MB

It’s terrible...

Code 2

object Solution {
    def isPalindrome(s:String):Boolean = {
        def palindromeLen(left:Int, right:Int):Int = {
            var l = left
            var r = right
            while(l >= 0 && r < s.length && s(l) == s(r)) {
                l = l-1
                r = r+1
            }
            r-l-1
        }
        var max = ""
        for {
            center <- 0 until s.length
        } {
            val oddLen = palindromeLen(center, center)
            val evenLen = palindromeLen(center, center+1)
            val tmpMax = if(oddLen > evenLen) oddLen else evenLen
            if(tmpMax > max.length) {
                max = s.slice(center-(tmpMax-1)/2, 1+center+tmpMax/2)
            }
        }
        max
    }
}

Methods

• Get index from 0 until given string length.
• Get longest palindromic substring length each index.
  • Case 1. Center is single character. ex). aba
  • Case 2. Center is two characters. ex). abba
• Find longest palindromic substring.

Results

Runtime: 496 ms, faster than 50.67% of Scala online submissions for Longest Palindromic Substring. Memory Usage: 56.2 MB, less than 87.50% of Scala online submissions for Longest Palindromic Substring.

Not Good, Not Bad.

Code 3

object Solution {
    def longestPalindrome(s: String): String = {
         val palindromeLen:(Int, Int) => Int = (left:Int, right:Int) => Iterator.from(0).collectFirst{
            case x if !(left-x >= 0 && right+x < s.length && s(left-x) == s(right+x)) => right-left+2*x-1
        }.get
        var max = ""
        for {
            center <- 0 until s.length
        } {
            val oddLen = palindromeLen(center, center)
            val evenLen = palindromeLen(center, center+1)
            val tmpMax = if(oddLen > evenLen) oddLen else evenLen
            if(tmpMax > max.length) {
                max = s.slice(center-(tmpMax-1)/2, 1+center+tmpMax/2)
            }
        }
        max
    }
}

Methods

It's almost the same Code 2, use Iterator and collectFirst instead of while.

Results

Runtime: 524 ms, faster than 53.03% of Scala online submissions for Longest Palindromic Substring. Memory Usage: 56 MB, less than 87.50% of Scala online submissions for Longest Palindromic Substring.