宫水三叶的刷题日记

V1

2022/06/18阅读:11主题:前端之巅同款

【宫水三叶的刷题日记】467. 环绕字符串中唯一的子字符串(中等)

题目描述

这是 LeetCode 上的 467. 环绕字符串中唯一的子字符串 ,难度为 中等

Tag : 「线性 DP」、「树状数组」

把字符串 s 看作是 “abcdefghijklmnopqrstuvwxyz” 的无限环绕字符串,所以 s 看起来是这样的:

"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...." .

现在给定另一个字符串 p 。返回 s 中 唯一 的 p 的 非空子串 的数量 。

示例 1:

输入: p = "a"

输出: 1

解释: 字符串 s 中只有一个"a"子字符。

示例 2:

输入: p = "cac"

输出: 2

解释: 字符串 s 中的字符串“cac”只有两个子串“a”、“c”。.

示例 3:

输入: p = "zab"

输出: 6

解释: 在字符串 s 中有六个子串“z”、“a”、“b”、“za”、“ab”、“zab”。

提示:

  • p 由小写英文字母构成

线性 DP + 树状数组 + 同字符最大长度计数

早上起来没睡醒 老了,脑袋不行了,第一反应是用「线性 DP + 树状数组」来做,估了一下时间复杂度没问题就写了。 该做法有一点点思维难度,因此可能不是这道中等题的标准解法。

定义 为以 为结尾的最大有效子串的长度。

从该状态定义容易得到如下的状态转移方程:

  • 存在 并且 能够接在 后面(除了 的下一字母以外,还特别包括 同时 的情况),则我们有
  • 不存在 或者 不能接在 后面,则有 ,含义为 只能自身组成子串。

与此同时,我们知道当结尾元素固定,子串长度固定,对应子串唯一确定。

当不考虑子串重复问题时,若 ,则以 为结尾的有效子串数量为 个(对应以 为结尾,长度范围为 的子数组)。

但实际上,我们不能统计相同的子串,因此我们需要考虑该如何去重。

不失一般性地,假设我们当前处理到字符串 p 中的第 位,以 为结尾的最大子串长度为

  • 此前如果 出现过 为结尾,长度「大于等于」 的子串的话,那么以 为结尾长度为 的子串必然已被统计,需要跳过。因此我们可以使用一个长度为 的数组 max,记录以每个字符 结尾的,出现过的最大子串长度为多少(当 max[s[i]] >= f[i] 时,跳过计数);
  • 此前如果 出现过 为结尾,长度「小于」 的子串的话,我们也不能直接统计累加 到答案上,这会导致那些以 为结尾,长度小于 的子串被重复计数,此时我们 需要知道在以 为结尾,长度为 范围内还有多少个子串尚未被统计,这可以使用「树状数组」解决:在 中总个数为 ,使用树状数组维护在 中已被统计的数的个数 ,那么 即是本次可增加的计数,计数完成后我们还需要在树状数组中的 位置增加 ,确保下次查询相同字符结尾长度不小于 的已覆盖子串数量时不会出错。

至此,我们通过「树状数组」+「记录同字符最大长度」的方式来分别解决「长度比 小」和「长度比 大」的重复子串统计问题。

代码:

class Solution {
    int N = 100010;
    int[][] trs = new int[26][N];
    int[] f = new int[N], max = new int[26];
    int n, ans;
    int lowbit(int x) {
        return x & -x;
    }
    void add(int[] tr, int x, int v) {
        for (int i = x; i <= n + 1; i += lowbit(i)) tr[i] += v;
    }
    int query(int[] tr, int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i];
        return ans;
    }
    public int findSubstringInWraproundString(String _p) {
        char[] cs = _p.toCharArray();
        n = cs.length; 
        for (int i = 0; i < n; i++) {
            int c = cs[i] - 'a';
            if (i == 0) {
                f[i] = 1;
            } else {
                int p = cs[i - 1] - 'a';
                if ((c == 0 && p == 25) || p + 1 == c) f[i] = f[i - 1] + 1;
                else f[i] = 1;
            }
            if (max[c] >= f[i]) continue;
            int cnt = f[i] - query(trs[c], f[i]);
            if (cnt == 0continue;
            ans += cnt;
            add(trs[c], f[i], cnt);
            max[c] = f[i];
        }
        return ans;
    }
}
  • 时间复杂度:
  • 空间复杂度: ,其中 为字符串 p 的字符集大小

线性 DP

对于相同的结尾字符 而言,如果在整个动规过程中的最大长度为 ,那么以 为结尾字符对答案的贡献为

基于此,我们只需保留解法一中的 max 数组即可,同时利用 只依赖于 进行更新,因此动规数组也可以使用一个变量来代替。

代码:

class Solution {
    public int findSubstringInWraproundString(String _p) {
        char[] cs = _p.toCharArray();
        int n = cs.length, ans = 0;
        int[] max = new int[26];
        max[cs[0] - 'a']++;
        for (int i = 1, j = 1; i < n; i++) {
            int c = cs[i] - 'a', p = cs[i - 1] - 'a';
            if ((p == 25 && c == 0) || p + 1 == c) j++;
            else j = 1;
            max[c] = Math.max(max[c], j);
        }
        for (int i = 0; i < 26; i++) ans += max[i];
        return ans;
    }
}
  • 时间复杂度:
  • 空间复杂度: ,其中 为字符串 p 的字符集大小

最后

这是我们「刷穿 LeetCode」系列文章的第 No.467 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

分类:

后端

标签:

数据结构与算法

作者介绍

宫水三叶的刷题日记
V1