Skip to content

Latest commit

 

History

History
173 lines (141 loc) · 5.36 KB

20200819-647.palindromic-substrings.md

File metadata and controls

173 lines (141 loc) · 5.36 KB

647.palindromic-substrings

题目链接：https://leetcode-cn.com/problems/palindromic-substrings/

参考链接：https://leetcode-cn.com/problems/balanced-binary-tree/solution/ping-heng-er-cha-shu-by-leetcode-solution/

题目

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1 :

输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2 :

输入："aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

  • 输入的字符串长度不会超过 1000 。

解题

思路[1]暴力遍历

  • 暴力遍历字符串，判断每个节点是不是回文字符串，如果是就++

代码

/**
 * @param {string} s
 * @return {number}
 */
const map = {};

const isPalindrome = function (s) {
  if(map.hasOwnProperty(s)){
    return map[s]
  }
  if (!s) return true;
  let start = 0;
  let end = s.length - 1;
  while (start < end) {
    if (s[start++] !== s[end--]) {
      map[s] = false;
      return false;
    }
  }
  map[s] = true;
  return true;
};

var countSubstrings = function(s) {
  let res = 0;
  for(let length = s.length; length > 0; length--){
    for(let i = 0; i <= s.length - length; i++){
      let str = s.slice(i, i + length);
      if(isPalindrome(str)){
        res++
      }
    }
  }
  return res
};

思路[2]回文中心判断

  • 因为回文串一定会有个回文中心，长度为n的回文串，回文中心一共有2n - 1个 长度为奇数的回文中心n长度为偶数的回文中心n - 1
    • 长度为奇数的回文中心，左侧起点为 i, 右侧起点为 i
    • 长度为偶数的回文中心，左侧起点为 i, 右侧起点为 i+1
  • 回文中心向外扩展，判断字符是否相等，一直到边界，或者不相等的时候，就拿到了该回文中心所有的回文串数量
  • 最后累加
/**
 * @param {string} s
 * @return {number}
 */
const match = (s, l, r) => {
  let ans = 0;
  // 回文中心向外扩展，判断该回文中心有多少回文串
  while (l >= 0 && r < s.length && s.charAt(l) == s.charAt(r)) {
    --l;
    ++r;
    ++ans;
  }
  return ans
}
var countSubstrings = function(s) {
  const n = s.length; // 长度用于计算回文中心
  let ans = 0; // 最终结果
  for (let i = 0; i < n; ++i) {
    // 回文中心一共 2n - 1 个 长度为奇数的回文中心 n 长度为偶数的回文中心 n - 1
    // 长度为奇数的回文中心，左侧起点为 i, 右侧起点为 i
    ans += match(s, i, i)
    // 长度为偶数的回文中心，左侧起点为 i, 右侧起点为 i+1
    ans += match(s, i, i + 1)
  }
  return ans;
};

思路[3]Manacher 算法，动态规划

  • 收集当前最长回文串的回文中心和这个回文串的右端点，这个回文中心和右端点的会随着当前回文串长度超过右端点而更新，这样就尽可能保证当前字符在回文串内不进行查询
  • 那么这个最大回文串要做什么呢，因为回文串的特性，当前回文中心a如果在一个回文串b内，那么，根据这个回文串b的回文中心，会存在一个对称点c，这个c在某种程度上和a是一个互为反转的关系，那么，如果以c为中心的回文串，在某些情况下，在a上也是回文串，这样如果要求a的情况，就可以在c的基础上进行判断
  • 那么为什么a和c不是完全一样的呢，因为，在最长回文串以内，左右两侧是相等的，这个时候可以相信这部分的回文串是两个一致的，但是，在这个回文串以外，就一定不一样了，所以这时就要取，a到最长回文串的右端点的长度了
  • 如果当前的回文中心，不在某个回文串内部，则认为是个新的起点，就初始化为1就可以
  • 当然，找到的这个长度，也是初始长度，而不是最终长度，因为回文串长度以外还可能会存在结果，所以要继续补充
  • 最后补充完毕以后，更新最长回文串的节点和右端点
  • 又因为判断回文中心会有奇偶的区别，所以在每个字符中插入一个#号，这样就不用考虑偶数的情况了，只是最后的结果要除2，向下取整

代码

/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function(s) {
  let n = s.length;
  // 首先填充字符串，去除奇偶情况
  let t = ['$', '#'];
  for (let i = 0; i < n; ++i) {
      t.push(s.charAt(i));
      t.push('#');
  }
  n = t.length;
  t.push('!');
  t = t.join('');
  // 开始整个流程
  const f = new Array(n); // 记录第i项的回文串长度，这个长度也就等于回文串数量
  let iMax = 0, rMax = 0, ans = 0;
  for (let i = 1; i < n; ++i) {
    // 初始化 f[i], 对称点 [2 * iMax - i]
    f[i] = i <= rMax ? Math.min(rMax - i + 1, f[2 * iMax - i]) : 1;
    // 中心拓展
    while (t.charAt(i + f[i]) == t.charAt(i - f[i])) {
      ++f[i];
    }
    // 动态维护 iMax 和 rMax，在发现当前字符的回文串超出最大右端点的时候，更新右端点和回文点
    if (i + f[i] - 1 > rMax) {
      iMax = i;
      rMax = i + f[i] - 1;
    }
    // 统计答案, 当前贡献为 (f[i] - 1) / 2 上取整
    ans += Math.floor(f[i] / 2);
  }
  return ans;
};

思考