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

回文

 2024/03/15 

题目(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)。

原文作者：Yizhou Shen

原文链接：http://shenyizhou.github.io/2024/03/15/2024-03-15-%E7%AE%97%E6%B3%95(34)-%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2/

发表日期：March 15th 2024, 11:32:11 pm

更新日期：March 17th 2024, 11:16:53 pm

Next Post

算法(35)-异次元星人的文字
Previous Post

算法(33)-检测回文字符串

CATALOG

1. 题目(easy)
2. 思路