5. Longest Palindromic Substring

最长回文子串问题

AC code

Approach #1

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  let longestLength = 0;
  let longestStr = '';
  for (let i = 0; i < s.length; i++) &#123;
    // 只看比最长的更长的
    for (let j = s.length - 1; j >= i + longestLength; j--) &#123;
      if (s[i] === s[j]) &#123;
        const str = s.substr(i, j - i + 1);
        if (validateString(str)) &#123;
          longestLength = str.length;
          longestStr = str;
        &#125;
      &#125;
    &#125;
  &#125;
  return longestLength ? longestStr : s ? s[0] : ''
&#125;;

const validateString = (str) => &#123;
  let i = 0,
    j = str.length - 1;
  while (i < j) &#123;
    if (str[i] !== str[j]) &#123;
      return false
    &#125;
    i++;
    j--;
  &#125;
  return true
&#125;;

Complexity Analysis

  • Time Complexity: O(N^2)

Approach #2

/**
 * @param &#123;string&#125; str
 * @return &#123;string&#125;
 */
var longestPalindrome = function (str) &#123;
  if (!str) &#123;
    return '';
  &#125;
  if (str.length === 1) &#123;
    return str;
  &#125;
  const newStr = '#' + str.split('').join('#') + '#';
  let p = new Array(newStr.length);
  p[0] = 1;
  let id = 0,
    mx = 0;

  for (let i = 1; i < newStr.length; i++) &#123;
    p[i] = mx > i ? Math.min(p[2 * id - i], mx - i) : 1;
    while (newStr[i + p[i]] === newStr[i - p[i]] && i - p[i] >= 0) &#123;
      p[i]++;
    &#125;
    if (i + p[i] > mx) &#123;
      mx = i + p[i];
      id = i;
    &#125;
  &#125;

  const res = p.reduce(
    (pre, ele, index) => &#123;
      if (ele > pre.value) &#123;
        pre.value = ele;
        pre.index = index;
      &#125;
      return pre;
    &#125;,
    &#123; value: 0, index: 0 &#125;
  );
  const substr = newStr.substr(res.index - res.value + 1, 2 * res.value - 1);
  return substr.split('#').join('');
&#125;;
Donate For A Cup Of Coffee...