目录
力扣467. 环绕字符串中唯一的子字符串
难度 中等
定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串，所以 base 看起来是这样的："...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".
给你一个字符串 s ，请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。
示例 1：
输入：s = "a" 输出：1 解释：字符串 s 的子字符串 "a" 在 base 中出现。
示例 2：
输入：s = "cac"
输出：2
解释：字符串 s 有两个子字符串 ("a", "c") 在 base 中出现。
示例 3：
输入：s = "zab"
输出：6
解释：字符串 s 有六个子字符串 ("z", "a", "b", "za", "ab", and "zab") 在 base 中出现。
提示：
1 <= s.length <= 10^5- s 由小写英文字母组成
class Solution {
public:
int findSubstringInWraproundString(string s) {
}
};解析代码
状态表示和状态转移方程：
以某个位置为结尾，结合题目要求，定义一个状态表示： dp[i] 表示：以 i 位置的元素为结尾的所有子串里面，有多少个在 base 中出现过。
对于 dp[i] ，我们可以根据子串的长度划分为两类：
- 子串的长度等于 1 ：因为只有小写字母，所以此时这个字符一定会出现在 base 中，dp[i] = 1;
- 子串的长度大于 1 ：如果 i 位置的字符和 i - 1 位置上的字符组合后，出现在 base 中的话，那么 dp[i - 1] 里面的所有子串后面填上一个 s[i] 依旧在 base 中出现。因此 dp[i] = dp[i - 1] ;
上面两种情况加起来， dp[i] = 1 + dp[i - 1] ，1是长度等于1的，其中 dp[i - 1] 是否加上需要先做一下判断。
初始化、填表顺序、返回值：
依题意，将表里面的值都初始化为 1 。 从左往右填表，这里不能直接返回 dp 表里面的和，因为会有重复的结果。在返回之前，我们需要先去重。
相同字符结尾的 dp 值，我们仅需保留最大的即可，其余 dp 值对应的子串都可以在最大的里面找到，那么可以创建一个大小为 26 的数组，统计所有字符结尾的最大 dp 值。 最后返回数组中所有元素的和即可。
class Solution {
public:
int findSubstringInWraproundString(string s) {
// dp[i] 表示以i位置的元素为结尾的所有子串里面，有多少个在 base 中出现过
int n = s.size();
vector<int> dp(n, 1);
vector<int> hash(26, 0);
for(int i = 1; i < n; ++i)
{
if(s[i] - 1 == s[i-1] || (s[i - 1] == 'z' && s[i] == 'a'))
dp[i] = dp[i-1] + 1;
}
// 计算每一个字符结尾的最⻓连续⼦数组的⻓度
for(int i = 0; i < n; ++i)
hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);
int sum = 0;
for(auto& e : hash)
sum += e;
return sum;
}
};
