Fastest JavaScript Solution


  • 0
    J

    Realize Manacher's Algorithm in JavaScript (132ms)

    Beats 100% JavaScript Submissions

     /**
     * @param {string} s
     * @return {string}
     */
    var longestPalindrome = function(s) {
      
      // Manacher's Algorithm
      
      // Justify if {string} s is totally palindrome string
      var i
        , len = Math.floor(s.length / 2) + 1
        , isTotalPalindrome = true
    
      for (i = 0; i < len; i++) {
        if (s[i] != s[s.length - i - 1]) {
          isTotalPalindrome = false
          break;
        }
      }
      
      if (isTotalPalindrome) return s;
      
      // preprocess, make {string} s must contain a palindrome of odd length
      s = [].join.call(s, '#')
      s = '$#' + s + '#$'
    
      var p = []
        , C = 1
        , R = 1
        , iMirror
        , max = 0
        , maxIndex
      
      for (i = 1; i < s.length - 1; i++) {
        iMirror = 2 * C - i
        p[i] = (R > i) ? Math.min(R - i, p[iMirror]) : 1
    
        while (s[i - p[i]] == s[i + p[i]]) p[i]++
    
        if (i + p[i] > R) {
          R = i + p[i]
          C = i
        }
    
        if (p[i] > max) {
          max = p[i]
          maxIndex = i
        }
      }
    
      return s.substr(maxIndex - max + 1, 2 * max - 1).replace(/[$#]/g, '')
    }

Log in to reply
 

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