剑指 Offer（专项突击版）第19|20题

站长

2023年03月18日 21:50 · 阅读数 43

前言

现在前端要求变高了,找工作的时可能会碰上算法题,每天刷几道算法题做足准备,今天是《剑指 Offer（专项突击版）》第19|20题。

剑指 Offer II 019. 最多删除一个字符得到回文

给定一个非空字符串 s，请判断如果最多从字符串中删除一个字符能否得到一个回文字符串。

难度：简单

示例 1:
输入: s = "aba" 输出: true 
示例 2:
输入: s = "abca" 输出: true 解释: 可以删除 "c" 字符 或者 "b" 字符 
示例 3:
输入: s = "abc" 输出: false

提示:
● 1 <= s.length <= 105
● s 由小写英文字母组成

知识点： 贪心双指针字符串

方法一：双指针

从字符串的两端开始向里逐步比较两个字符是不是相同。

如果相同，则继续向里移动指针比较里面的两个字符。

如果不相同，按照题目的要求，在删除一个字符之后再比较其他的字符就能够形成一个回文。由于不知道删除两个不同字符中的哪一个，因此两个字符都可以进行尝试。

/**
 * @param {string} s
 * @return {boolean}
 */
var validPalindrome = function(s) {
    //头尾指针
    let l = 0, r = s.length - 1; 
    while (l < r) {
        if (s[l] != s[r]) {
            //左右指针不一样 有一次删除机会
            //左指针往右一步或右指针向左一步继续验证
            return isPalindrome(s, l + 1, r) || isPalindrome(s, l, r - 1);
        }
        l++;
        r--;
    }
    return true;
};

function isPalindrome(str, l, r) {
    while (l < r) {   
        //判断两边的数字是否相等         
        if (str[l] != str[r]) {
            return false;
        }
        l++;
        r--;
    }
    return true;
}

复杂度分析

时间复杂度：O(n)，其中 n 是字符串的长度。判断整个字符串是否是回文字符串的时间复杂度是 O(n)，遇到不同字符时，判断两个子串是否是回文字符串的时间复杂度也都是 O(n)。
空间复杂度：O(1)。只需要维护有限的常量空间。

剑指 Offer II 020. 回文子字符串的个数

给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。

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

难度：中等

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

提示：
● 1 <= s.length <= 1000
● s 由小写英文字母组成

知识点： 字符串动态规划

方法一：中心拓展

计算有多少个回文子串的最朴素方法就是枚举出所有的回文子串，有两种思路，分别是：

枚举出所有的子串，然后再判断这些子串是否是回文；
枚举每一个可能的回文中心，然后用两个指针分别向左右两边拓展，当两个指针指向的元素相同的时候就拓展，否则停止拓展。

假设字符串的长度为 n。1会用 (n^2) 的时间枚举出所有的子串 ]，然后再用 O(ri−li+1)的时间检测当前的子串是否是回文，整个算法的时间复杂度是 O(n^3)。而2枚举回文中心的是 O(n) 的，对于每个回文中心拓展的次数也是 O(n) 的，所以时间复杂度是 O(n^2)。所以我们选择第二种方法来枚举所有的回文子串。

例如，在字符串"abcba"中，从中间的"c"出发向两端延伸一个字符，由于"c"前后都是字符'b'，因此找到了一个长度为3的回文子字符串"bcb"。然后向两端延伸一个字符，由于"bcb"的前后都是字符'a'，因此又找到一个长度为5的回文子字符串"abcba"。

注意，回文的长度既可以是奇数，也可以是偶数。长度为奇数的回文的对称中心只有一个字符，而长度为偶数的回文的对称中心有两个字符。

/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function(s) {
    if(s === null || s.length === 0) {
        return 0;
    }
    let count = 0;
    for(let i = 0; i < s.length; i++) {
        count += countPalindrome(s, i, i);
        count += countPalindrome(s, i, i + 1);
    }
    return count;
};

function countPalindrome (str, l, r) {
    let count = 0;
    while (l >= 0 && r <=str.length && str.charAt(l) == str.charAt(r)) {
        count++;
        l--;
        r++;
    }
    return  count;
}

复杂度分析

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

方法二：动态规划

状态：dp[i][j] 表示字符串s在[i,j]区间的子串是否是一个回文串。
状态转移方程：当 s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1]) 时，dp[i][j]=true，否则为false

状态转移方程解释：

当只有一个字符时，比如 a 自然是一个回文串。

当有两个字符时，如果是相等的，比如 aa，也是一个回文串。

当有三个及以上字符时，比如 ababa 这个字符记作串 1，把两边的 a 去掉，也就是 bab 记作串 2，可以看出只要串2是一个回文串，那么左右各多了一个 a 的串 1 必定也是回文串。所以当 s[i]==s[j] 时，自然要看 dp[i+1][j-1] 是不是一个回文串。

const countSubstrings = (s) => {
  let count = 0;
  const len = s.length;

  const dp = new Array(len);
  for (let i = 0; i < len; i++) {
    // 二维矩阵
    dp[i] = new Array(len).fill(false); 
  }

  for (let j = 0; j < len; j++) { 
    // 注意扫描矩阵的方向
    for (let i = 0; i <= j; i++) {
      if (i == j) {   
        // 单个字符的情况
        dp[i][j] = true;
        count++;
      } else if (j - i == 1 && s[i] == s[j]) { 
        // 两个字符的情况 
        dp[i][j] = true;
        count++;
      } else if (j - i > 1 && s[i] == s[j] && dp[i + 1][j - 1]) {
        // 多于两个字符
        dp[i][j] = true;
        count++;
      }
    }
  }
  return count;
};

复杂度分析：

时间复杂度：O(n^2)
空间复杂度：O(n^2)

so

剑指 Offer（专项突击版）第19|20题

传送门

转载自:https://juejin.cn/post/7180340867385786405