647. 回文子串

647. 回文子串

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：
输入：s = “abc” 输出：3 解释：三个回文子串: “a”, “b”, “c”
示例 2：
输入：s = “aaa” 输出：6 解释：6 个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

提示：

• 1 <= s.length <= 1000
• s 由小写英文字母组成

思路

暴力判断模拟即可，用空间换时间。另外一种，寻找回文中心，分别判断奇数长度回文子串及偶数长度回文子串的情况。

解答

/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function (s) {
  const set = new Set();
  let res = 0;
  const judge = (str) => {
    let left = 0,
      right = str.length - 1;
    while (left < right) {
      if (str[left++] !== str[right--]) return false;
    }
    return true;
  };
  for (let i = 0; i < s.length; i++) {
    for (let j = i + 1; j <= s.length; j++) {
      const str = s.slice(i, j);
      if (set.has(str)) {
        res++;
        continue;
      }
      if (str.length === 1 || judge(str)) {
        set.add(str);
        res++;
      }
    }
  }
  return res;
};

/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function (s) {
  let res = 0;

  const judge = (left, right) => {
    let count = 0;
    while (left >= 0 && right < s.length) {
      if (s[left] !== s[right]) break;
      count++;
      left--;
      right++;
    }
    return count;
  };

  for (let i = 0; i < s.length; i++) {
    res += judge(i, i) + judge(i, i + 1);
  }

  return res;
};