动态规划：环绕字符串中唯一的子字符串

环绕字符串中唯一的子字符串

题目来源： 力扣 467. 环绕字符串中唯一的子字符串

题目解析

（此处省略图片，保留核心逻辑）

算法原理

状态表示

以 i 位置为结尾的所有子串中，有多少个在 base（包含所有小写字母）中出现过。

状态转移方程

dp[i] 分为两种情况：

1. 长度为 1：1
2. 长度大于 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;
    }
};