• https://leetcode.com/problems/longest-palindromic-substring/description/
• 5. Longest Palindromic Substring

JavaScript 解答

var longestPalindrome = function (s) {
    var a = new Date();
    var n = s.length;
    var res = '';
    var dp = [];
    while (dp.push(new Array(n).fill(-1)) < n);
    // console.log(dp);

    for (var i = n - 1; i >= 0; i--) {
        for (var j = i; j < n; j++) {
            dp[i][j] = s[i] === s[j] && ((j - i < 3) || dp[i + 1][j - 1]);
            if (dp[i][j] === undefined) {
                console.log(i, j, s[i], s[j], dp[i + 1][j - 1])
            }
            if (dp[i][j]) {
                var tmp = s.substring(i, j + 1);
                if (tmp.length > res.length) res = tmp;
            }

        }
    }
    // console.log(dp);
    console.log(new Date() - a);

    return res;
};

Ruby 解答

def expand(s, center)  
  li, ri = center.floor, center.ceil  
  if li == ri  
      li -= 1  
      ri += 1  
  end  
  left_space = li  
  right_space = s.length - ri - 1  
  max_space = [left_space, right_space].min  
  most_left = li - max_space  
  while li >= most_left do  
    if s[li] == s[ri]  
      li -= 1  
      ri += 1  
    else  
      break  
    end  
  end  
  [ri - li - 1, li + 1, ri - 1]  
end  
  
def longest_palindrome(s)  
  i = 0  
  max_si, max_ei, max_len = nil, nil, 0  
  while i <= s.length - 1 do  
    len, si, ei = expand(s, i)  
    if max_len < len  
        max_si, max_ei, max_len = si, ei, len  
    end  
    i += 0.5  
  end  
  s[max_si..max_ei]
end