AC Javascript version


  • 0
    F

    I don't know why but a plain O(n^2) algorithm gets TLE so I wrote a theoretically O(n^2) but on average nearly O(n) code. Key idea is that

    1. X is palindrome <==> aXa is also palindrome.
    2. X is made of only one character c <==> Xc is also a palindrome made of only c.
    3. any single character itself is a palindrome string of length=1.

    So we can get new possible palindrome ending at i based on palindrome ending at i-1.

    Coffeescript code:

    longestPalindrome = (s) ->
      bestOffset = 0
      bestLength = 1
    
      onlyOneChar =
        prevLength: 1
        prevSingleCharacter: true
    
      prevPossibilities = [onlyOneChar]
    
      for i in [1...s.length]
        allPossibilities = [onlyOneChar]
        for {prevLength, prevSingleCharacter} in prevPossibilities
          # the start index of the previous palindrome
          prevStart = i-prevLength
          len = 0
          if prevStart >= 1 and s[i] is s[prevStart-1]
            # constructing "a{prev}a" type of palindrome
            len = prevLength + 2
            singleCharacter = prevSingleCharacter and s[i] is s[i-1]
          else if prevStart >= 0 and s[i] is s[prevStart] and prevSingleCharacter
            # constructing "{aaaaa}a" type of palindrome
            len = prevLength + 1
            singleCharacter = true
          if len > 0
            if len > bestLength
              bestLength = len
              bestOffset = i
            allPossibilities.push
              prevLength: len
              prevSingleCharacter: singleCharacter
        prevPossibilities = allPossibilities
      
      return s.substr(bestOffset-bestLength+1, bestLength)

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.