本文主要是介绍每日OJ题_子数组子串dp⑧_力扣467. 环绕字符串中唯一的子字符串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
力扣467. 环绕字符串中唯一的子字符串
解析代码
力扣467. 环绕字符串中唯一的子字符串
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;}
};这篇关于每日OJ题_子数组子串dp⑧_力扣467. 环绕字符串中唯一的子字符串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
