关注Java领域相关技术 记录有趣的事情

LeetCode-647. 回文子串

US-B.Ralph
US-B.Ralph
2020-08-19

问题地址

LeetCode每日一题/2020-08-19

LeetCode647. 回文子串

问题描述

规则

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

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

示例1

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

示例2

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

提示

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

解析

解题思路

回文子串是一个正读和反读都一样的字符串，比如“level”或者“noon”等就是回文串。
题目规定：具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。
可以采用暴力破解法，列出所有子串，判断子串是否为回文子串；

复杂度分析

  1. 时间复杂度，列举所有子串的时间复杂度为O(n^2)，判断子串是否为回文子串的时间复杂度为O(subStr.length/2)，故总体时间发杂度为O(n^3)；

  2. 空间复杂度，本例使用哈希表存储每个字符数量，故极端情况空间复杂度为O(n)；

定位问题

  1. 找出所有回文子串；

数据操作分析

  1. 遍历字符串找出所有字符串子串；
  2. 判断字符串子串是否为回文子串；

编码实现

/**
 * LeetCode647
 */
class Solution {
    public int countSubstrings(String s) {
        if (s.equals("") || s == null) return 0;
        if (s.length() == 1) return 1;

        int count = 0;
        HashMap<Character, Integer> map = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.get(c) == null) {
                map.put(s.charAt(i), 1);
            } else {
                int n = map.get(c) + 1;
                map.put(c, n);
            }
        }
        if (s.length() == map.size()) return s.length();

        if (map.size() == 1) return length((Integer) map.values().toArray()[0]);

        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                String subStr = s.substring(i, j);
                if (isPalindrome(subStr)) {
                    count++;
                }
            }
        }

        return count;
    }

    private boolean isPalindrome(String subStr) {
        if (subStr.length() == 1) return true;
        if ((subStr.length() == 2 || subStr.length() == 3) && subStr.charAt(0) == subStr.charAt(subStr.length() - 1))
            return true;
        if (!(subStr.charAt(0) == subStr.charAt(subStr.length() - 1))) return false;
        int i = 0;
        int j = subStr.length() - 1;
        while (i <= j) {
            String a = subStr.substring(i, i + 1);
            String b = subStr.substring(j, j + 1);
            if (!a.equals(b)) return false;
            i++;
            j--;
        }
        return true;
    }

    private int length(Integer num) {
        if (num == 0 || num == 1) return num;
        return num * (1 + num) / 2;
    }

}

官方解法

  1. 中心拓展
  • 思路：
    • 计算有多少个回文子串的最朴素方法就是枚举出所有的回文子串，而枚举出所有的回文字串又有两种思路，分别是：
      • 枚举出所有的子串，然后再判断这些子串是否是回文；
      • 枚举每一个可能的回文中心，然后用两个指针分别向左右两边拓展，当两个指针指向的元素相同的时候就拓展，否则停止拓展。
    • 假设字符串的长度为 n。我们可以看出前者会用 O(n^2) 的时间枚举出所有的子串 s[l_i⋯r_i]，然后再用 O(r_i−l_i+1) 的时间检测当前的子串是否是回文，整个算法的时间复杂度是 O(n^3)。而后者枚举回文中心的是 O(n) 的，对于每个回文中心拓展的次数也是 O(n) 的，所以时间复杂度是 O(n^2)。所以我们选择第二种方法来枚举所有的回文子串。

    • 在实现的时候，我们需要处理一个问题，即如何有序地枚举所有可能的回文中心，我们需要考虑回文长度是奇数和回文长度是偶数的两种情况。如果回文长度是奇数，那么回文中心是一个字符；如果回文长度是偶数，那么中心是两个字符。当然你可以做两次循环来分别枚举奇数长度和偶数长度的回文，但是我们也可以用一个循环搞定。我们不妨写一组出来观察观察，假设 n=4，我们可以把可能的回文中心列出来：

      编号i 回文中心左起始位置 l_i 回文中心右起始位置 r_i
      0 0 0
      1 0 1
      2 1 1
      3 1 2
      4 2 2
      5 2 3
      6 3 3
    • 由此我们可以看出长度为 n 的字符串会生成 2n-1 组回文中心 [l_i,r_i]，其中 l_i=[ \frac{i}{2}], r_i=l_i+(i mod 2)。这样我们只要从 0 到 2n – 2 遍历 i，就可以得到所有可能的回文中心，这样就把奇数长度和偶数长度两种情况统一起来了。

  • 复杂度分析：

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

    • 空间复杂度：O(1)。

class Solution {
    public int countSubstrings(String s) {
        int n = s.length(), ans = 0;
        for (int i = 0; i < 2 * n - 1; ++i) {
            int l = i / 2, r = i / 2 + i % 2;
            while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
                --l;
                ++r;
                ++ans;
            }
        }
        return ans;
    }
}
  1. Manacher 算法

  • 思路：

    • Manacher 算法是在线性时间内求解最长回文子串的算法。在本题中，我们要求解回文串的个数，为什么也能使用 Manacher 算法呢？这里我们就需要理解一下 Manacher 的基本原理。
    • Manacher 算法也会面临「方法一」中的奇数长度和偶数长度的问题，它的处理方式是在所有的相邻字符中间插入 #，比如 abaa 会被处理成 #a#b#a#a#，这样可以保证所有找到的回文串都是奇数长度的，以任意一个字符为回文中心，既可以包含原来的奇数长度的情况，也可以包含原来偶数长度的情况。假设原字符串为 S，经过这个处理之后的字符串为 s。
    • 我们用 f(i) 来表示以 s 的第 i 位为回文中心，可以拓展出的最大回文半径，那么 f(i)−1 就是以 i 为中心的最大回文串长度 （想一想为什么）。
    • Manacher 算法依旧需要枚举 s 的每一个位置并先假设它是回文中心，但是它会利用已经计算出来的状态来更新 f(i)，而不是向「中心拓展」一样盲目地拓展。具体地说，假设我们已经计算好了 [1,i−1] 区间内所有点的 f（即我们知道 [1,i−1] 这些点作为回文中心时候的最大半径）， 那么我们也就知道了 [1,i−1] 拓展出的回文达到最大半径时的回文右端点。例如 i=4 的时候 f(i)=5，说明以第 4 个元素为回文中心，最大能拓展到的回文半径是 5，此时右端点为 4+5−1=8。所以当我们知道一个 i 对应的 f(i) 的时候，我们就可以很容易得到它的右端点为 i+f(i)−1。

    • Manacher 算法如何通过已经计算出的状态来更新 f(i) 呢？Manacher 算法要求我们维护「当前最大的回文的右端点 r_m 」以及这个回文右端点对应的回文中心 i_m 。我们需要顺序遍历 s，假设当前遍历的下标为 i。我们知道在求解 f(i) 之前我们应当已经得到了从 [1,i−1] 所有的 f，并且当前已经有了一个最大回文右端点 r_m 以及它对应的回文中心 i_m.
    • 初始化 f(i)
      • 如果 i≤r_m ，说明 i 被包含在当前最大回文子串内，假设 j 是 i 关于这个最大回文的回文中心 i_m 的对称位置（即 j+i=2×i_m ），我们可以得到 f(i) 至少等于 min(f(j),r_m−i+1)。这里将 f(j) 和 r_m – i + 1 取小，是先要保证这个回文串在当前最大回文串内。（思考：为什么 f(j) 有可能大于 r_m – i + 1 ？）
      • 如果 i>r_m ，那就先初始化 f(i) = 1。
    • 中心拓展
      • 做完初始化之后，我们可以保证此时的 s[i+f(i)−1]=s[i−f(i)+1]，要继续拓展这个区间，我们就要继续判断 s[i+f(i)] 和 s[i – f(i)] 是否相等，如果相等将 f(i) 自增；这样循环直到 s[i + f(i)] \neq s[i – f(i)]，以此类推。我们可以看出循环每次结束时都能保证 s[i + f(i) – 1] = s[i – f(i) + 1]，而循环继续（即可拓展的条件）一定是 s[i + f(i)] = s[i – f(i)]。 这个时候我们需要注意的是不能让下标越界，有一个很简单的办法，就是在开头加一个 $ ，并在结尾加一个 ! ，这样开头和结尾的两个字符一定不相等，循环就可以在这里终止。
    • 这样我们可以得到 s 所有点为中心的最大回文半径，也就能够得到 S 中所有可能的回文中心的的最大回文半径，把它们累加就可以得到答案。
  • 复杂度分析：
    • 时间复杂度：O(n)，即 Manacher 算法的时间复杂度，由于最大回文右端点 r_m 只会增加而不会减少，故中心拓展进行的次数最多为 O(n)，此外我们只会遍历字符串一次，故总复杂度为 O(n)。

    • 空间复杂度：O(n)。

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        StringBuffer t = new StringBuffer("$#");
        for (int i = 0; i < n; ++i) {
            //保证所有找到的回文字符串都是奇数长度
            t.append(s.charAt(i));
            t.append('#');
        }
        n = t.length();
        t.append('!');

        int[] f = new int[n];
        //iMax为右侧回文中心点，rMax为右侧回文最右侧
        int iMax = 0, rMax = 0, ans = 0;
        for (int i = 1; i < n; ++i) {
            // 初始化 f[i]，f[i]=min(i到最右回文边界 , 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 += f[i] / 2;
        }

        return ans;
    }
}

精彩评论补充

1. 动态规划思路

  • 有时候我们想到了 DP 但想不出来，可以试试这么入手：
    • 大问题是什么？
    • 规模小一点的子问题是什么？
    • 它们之间有什么联系？
  • 大问题是一个字符串是否是回文串，那规模小一点的子问题呢？
    • 一个字符串是回文串，它的首尾字符相同，且剩余子串必须是一个回文串。
    • 剩余子串是否为回文串，就是规模小一点的子问题，它的结果影响大问题的结果。
  • 那我们怎么去描述这个子问题呢？
    • 很显然，一个子串由两端的指针确定，i 、j 就是描述子问题的变量，子串 s[i:j]s 是否是回文串，就是一个子问题。
    • 我们用二维数组记录计算过的子问题的结果，从base case出发，像填表一样递推出每个子问题的解。别忘了 i<=j，只用计算半张 dp 表格，如下图：
  • 我们罗列一下dp[i][j]为 true 的情形：（具体状态转移方程比较简单，见代码吧）
    • 由单个字符组成。
    • 由 2 个字符组成，且字符要相同。
    • 由多于 2 个字符组成，首尾字符相同，且剩余子串是一个回文串。
  • 复杂度分析：
    • 时间复杂度：O(n^2)。

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

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;
};

再弄个图看看状态转移的方向，所以从左上角开始的计算方向，可以保证计算 dp[i][j]时dp[i + 1][j – 1]肯定计算过了。扫描的方向是一个容易困惑、容易出 bug 的点。

US-B.Ralph
LeetCode数据结构与算法算法

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注

4 × 3 =