【面试高频题】难度 1.5/5，常见字符串线性 DP 运用题
【面试高频题】难度 1.5/5，常见字符串线性 DP 运用题
题目描述
这是 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 == 0) continue;
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 原题链接和其他优选题解。
腾讯云开发者
