算法(34)-最长回文子串

题目(easy)

给你一个字符串s，找到s中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

输入格式:
1<=s.length<=1000

输出格式:
s中最长的回文子串

输入样例:
在这里给出一组输入。例如：

zyrcbabd
输出样例:
在这里给出相应的输出。例如：

bab

思路

var fs = require('fs');
var buf = '';

function findLongestPlindrome(str) {
  const len = str.length;
  let res = '';
  for(let i = 0; i < 2 * len - 1; i++) {
    let left = Math.floor(i / 2);
    let right = left + i % 2;
    let temp = left === right ? 1 : 2;
    while(left >= 0 && right < len && str[left] === str[right]) {
      left--;
      right++;
      temp+=2;
    }
    if (temp - 2 > res.length) {
        res = str.slice(left + 1, right);
    }
    if (res.length === len) {
      break;
    }
  }
  return res;
}

process.stdin.on('readable', function() {
  var chunk = process.stdin.read();
  if (chunk) buf += chunk.toString();
});

process.stdin.on('end', function() {
  buf.split('\n').forEach(function(line) {
      if (line) {
        console.log(findLongestPlindrome(line));
      }
  });
});

时间复杂度: O(n^2)。
空间复杂度: O(1)。