共计 2885 个字符,预计需要花费 8 分钟才能阅读完成。
题目形容
这是 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”。
提醒:
- $1 <= p.length <= 10^5$
p
由小写英文字母形成
线性 DP + 树状数组 + 同字符最大长度计数
早上起来没睡醒老了,脑袋不行了,第一反馈是用「线性 DP + 树状数组」来做,估了一下工夫复杂度没问题就写了。
该做法有一点点思维难度,因而可能不是这道中等题的规范解法。
定义 $f[i]$ 为以 $s[i]$ 为结尾的最大无效子串的长度。
从该状态定义容易失去如下的状态转移方程:
- 存在 $s[i – 1]$ 并且 $s[i]$ 可能接在 $s[i – 1]$ 前面(除了 $s[i]$ 为 $s[i – 1]$ 的下一字母以外,还特地包含 $s[i – 1] = z$ 同时 $s[i] = a$ 的状况),则咱们有 $f[i] = f[i – 1] + 1$;
- 不存在 $s[i – 1]$ 或者 $s[i]$ 不能接在 $s[i – 1]$ 前面,则有 $f[i] = 1$,含意为 $s[i]$ 只能本身组成子串。
与此同时,咱们晓得当结尾元素固定,子串长度固定,对应子串惟一确定。
当不思考子串反复问题时,若 $f[i] = k$,则以 $s[i]$ 为结尾的无效子串数量为 $k$ 个(对应以 $s[i]$ 为结尾,长度范畴为 $[1, k]$ 的子数组)。
但实际上,咱们不能统计雷同的子串,因而咱们须要思考该如何去重。
不失一般性地,假如咱们以后解决到字符串 p
中的第 $i$ 位,以 $s[i]$ 为结尾的最大子串长度为 $f[i]$:
- 此前如果 呈现过 以 $s[i]$ 为结尾,长度「大于等于」$f[i]$ 的子串的话,那么以 $s[i]$ 为结尾长度为 $f[i]$ 的子串必然已被统计,须要跳过。因而咱们能够应用一个长度为 $26$ 的数组
max
,记录以每个字符 $s[i]$ 结尾的,呈现过的最大子串长度为多少(当max[s[i]] >= f[i]
时,跳过计数); - 此前如果 呈现过 以 $s[i]$ 为结尾,长度「小于」$f[i]$ 的子串的话,咱们也不能间接统计累加 $f[i]$ 到答案上,这会导致那些以 $s[i]$ 为结尾,长度小于 $f[i]$ 的子串被反复计数,此时咱们 须要晓得在以 $s[i]$ 为结尾,长度为 $[1, f[i]]$ 范畴内还有多少个子串尚未被统计,这能够应用「树状数组」解决:在 $[1, f[i]]$ 中总个数为 $a = f[i]$,应用树状数组保护在 $[1, f[i]]$ 中已被统计的数的个数 $b$,那么 $cnt = a – b$ 即是本次可减少的计数,计数实现后咱们还须要在树状数组中的 $f[i]$ 地位减少 $cnt$,确保下次查问雷同字符结尾长度不小于 $f[i]$ 的已笼罩子串数量时不会出错。
至此,咱们通过「树状数组」+「记录同字符最大长度」的形式来别离解决「长度比 $f[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 >= f[i]) continue;
int cnt = f[i] - query(trs, f[i]);
if (cnt == 0) continue;
ans += cnt;
add(trs, f[i], cnt);
max = f[i];
}
return ans;
}
}
- 工夫复杂度:$O(n\log{n})$
- 空间复杂度:$O(C \times n)$,其中 $C = 26$ 为字符串
p
的字符集大小
线性 DP
对于雷同的结尾字符 $c$ 而言,如果在整个动规过程中的最大长度为 $len$,那么以 $c$ 为结尾字符对答案的奉献为 $len$。
基于此,咱们只需保留解法一中的 max
数组即可,同时利用 $f[i]$ 只依赖于 $f[i – 1]$ 进行更新,因而动规数组也能够应用一个变量来代替。
代码:
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 = Math.max(max, j);
}
for (int i = 0; i < 26; i++) ans += max[i];
return ans;
}
}
- 工夫复杂度:$O(n)$
- 空间复杂度:$O(C)$,其中 $C = 26$ 为字符串
p
的字符集大小
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.467
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,局部是有锁题,咱们将先把所有不带锁的题目刷完。
在这个系列文章外面,除了解说解题思路以外,还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码,我建设了相干的仓库:https://github.com/SharingSou…。
在仓库地址里,你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
本文由 mdnice 多平台公布