本文主要是介绍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刷题详解——环绕字符串中唯一的子字符串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!