环绕字符串中唯一的子字符串
题目来源: 力扣 467. 环绕字符串中唯一的子字符串
题目解析
(此处省略图片,保留核心逻辑)
算法原理
状态表示
以 i 位置为结尾的所有子串中,有多少个在 base(包含所有小写字母)中出现过。
状态转移方程
dp[i] 分为两种情况:
- 长度为 1:1
- 长度大于 1:当 s[i-1] + 1 == s[i] || s[i-1] == 'z' && s[i] == 'a' 时,dp[i] = 1 + dp[i-1]
初始化
把数组里的值全部初始化为 1。
填表顺序
从左往右。
返回值
不能直接返回 dp 表里所有元素的和,因为会重复计算。需要先进行去重,统计以每个字符结尾的最大连续子串长度之和。
代码
class Solution {
public:
int findSubstringInWraproundString(string s) {
int n = s.size();
vector<int> dp(n, 1);
for(int i = 1; i < n; i++) {
if(s[i-1]+1==s[i]||s[i-1]=='z'&&s[i]=='a') {
dp[i] += dp[i-1];
}
}
//定义一个哈希表去重
int hash[26]={0};
for(int i=0;i<n;i++) {
hash[s[i]-'a']=max(hash[s[i]-'a'],dp[i]);
}
int sum=;
( x:hash) sum+=x;
sum;
}
};


