本文主要是介绍Leetcode刷题详解——环绕字符串中唯一的子字符串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1. 题目链接：467. 环绕字符串中唯一的子字符串
2. 题目描述：
定义字符串
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 <= 105- s 由小写英文字母组成
3. 解法（动态规划）：
3.1 算法思路：
1. 状态表示：
dp[i]表示：以 i位置的元素为结尾的所有子串里面，有多少个在 base中出现过
2. 状态转移方程：
对于 dp[i]，我们可以根据子串的长度划分为两类：
- 子串的长度等于1：此时这一个字符会出现在
base中 - 子串的长度大于1：如果
i位置的字符和i-1位置上的字符组合后，出现在base中的话，那么dp[i-1]里面的所有子串后面填上一个s[i]依旧在base中出现，因此dp[i]=dp[i-1]
综上，dp[i]=1+dp[i-1]，其中 dp[i-1]是否加上需要先做一下判断
3. 初始化：
将表里面的值都初始化为1
4. 填表顺序：
从左往右
5. 返回值：
这里不能直接返回 dp表里面的和，因为会又重复的结果。在返回之前，我们需要先去重：
- 相同字符结尾的
dp值，我们仅需要保留最大的即可，其余dp值对应的子串都可以在最大的里面找到 - 可以创建一个大小为26的数组，统计所有字符结尾的最大
dp值 - 最后返回数组中所有元素的和即可
3.2 C++算法代码：
class Solution {
public:int findSubstringInWraproundString(string s) {// 获取字符串长度int n = s.size();// 初始化动态规划数组，dp[i]表示以第i个字符结尾的最长连续子串的长度vector<int> dp(n, 1);// 遍历字符串，从第二个字符开始for (int i = 1; i < n; i++) {// 如果当前字符与前一个字符相差1或者当前字符是'z'且前一个字符是'a'，则说明可以组成连续子串if (s[i] - 1 == s[i - 1] || (s[i - 1] == 'z' && s[i] == 'a')) {// 更新dp数组dp[i] = dp[i - 1] + 1;}}// 初始化哈希数组，用于记录每个字符作为子串末尾时的最大长度int hash[26] = {0};// 遍历dp数组，更新哈希数组for (int i = 0; i < n; i++) {hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);}// 计算所有子串长度之和int sum = 0;for (auto x : hash) sum += x;return sum;}
};
这篇关于Leetcode刷题详解——环绕字符串中唯一的子字符串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
