最长回文子串查找代码内存溢出问题排查

问题描述 #

以下JavaScript代码用于查找字符串的最长回文子串，在测试示例"abaxyzzyxf"中能正确输出xyzzyx，但在测试环境运行时触发内存溢出错误，问题根源何在？

原代码 #

function longestPalindromicSubstring(string) {
  let longestPalindrome = "";

  let left = 0;
  let right = 0;

  // 查找奇数长度回文
  for (let index = 0; index < string.length; index++) {
    left = right = index;
    while (string[left] === string[right]) {
      if (right - left + 1 >= longestPalindrome.length) {
        longestPalindrome = string.substring(left, right + 1);
      }
      left--;
      right++;
    }
  }

  // 查找偶数长度回文
  for (let index = 0; index < string.length; index++) {
    left = index;
    right = left + 1;
    while (string[left] === string[right]) {
      if (right - left + 1 >= longestPalindrome.length) {
        longestPalindrome = string.substring(left, right + 1);
      }
      left--;
      right++;
    }
  }

  return longestPalindrome;
}

console.log(longestPalindromicSubstring("abaxyzzyxf"));

内存溢出原因 #

while循环缺少边界判断：当left递减到-1，或者right递增到超过字符串长度时，string[left]和string[right]都会变成undefined，而undefined === undefined的结果为true，导致循环无限执行。在无限循环过程中，代码会不断执行string.substring创建新字符串，持续占用内存，最终触发内存溢出。

修复后的代码 #

在两个while循环的条件中，增加对left和right的边界校验，确保它们始终在字符串索引范围内：

function longestPalindromicSubstring(string) {
  let longestPalindrome = "";

  let left = 0;
  let right = 0;

  // 查找奇数长度回文
  for (let index = 0; index < string.length; index++) {
    left = right = index;
    // 增加边界判断
    while (left >= 0 && right < string.length && string[left] === string[right]) {
      if (right - left + 1 >= longestPalindrome.length) {
        longestPalindrome = string.substring(left, right + 1);
      }
      left--;
      right++;
    }
  }

  // 查找偶数长度回文
  for (let index = 0; index < string.length; index++) {
    left = index;
    right = left + 1;
    // 增加边界判断
    while (left >= 0 && right < string.length && string[left] === string[right]) {
      if (right - left + 1 >= longestPalindrome.length) {
        longestPalindrome = string.substring(left, right + 1);
      }
      left--;
      right++;
    }
  }

  return longestPalindrome;
}

console.log(longestPalindromicSubstring("abaxyzzyxf"));

内容的提问来源于stack exchange，提问作者Cody