【学会动态规划】环绕字符串中唯一的子字符串（25）

动态规划怎么学？

学习一个算法没有捷径，更何况是学习动态规划，

跟我一起刷动态规划算法题，一起学会动态规划！

1. 题目解析

题目链接：467. 环绕字符串中唯一的子字符串 - 力扣（LeetCode）

这道题目也很好理解，读一遍基本就理解了，就是找他给的示例中，

有多少不同的非空子串在 base 里出现，base 就是 a ~ z a ~ z 的一个无线循环。

2. 算法原理

1. 状态表示

dp[ i ] 表示以 i 位置为结尾的所有子串里面，有多少个在 base 中出现过。

2. 状态转移方程

这里就可以分成两种情况：

如果长度为1，则 dp[ i ] = 1

如果长度大于 1 ，证明 i 位置与前面的位置结合了，那么如果：

s[ i - 1 ] + 1 == s[ i ] || ( s[ i - 1 ] == 'z' && s[ i ] == 'a' )，dp[ i ] = dp[ i - 1 ]

（之前有多少种情况，现在就有多少种情况）

因为求的是所有的情况的和，所以状态转移方程就是：

dp[ i ] = 1 + s[ i - 1 ] + 1 == s[ i ] || ( s[ i - 1 ] == 'z' && s[ i ] == 'a' ) ? dp[ i ] = dp[ i - 1 ] : 0

3. 初始化

因为每个字母一定会出现，所以我们可以直接把数组初始化成 1 ，

这样我们的状态转移方程就不用多加那个 1 了。

4. 填表顺序

从左往右。

5. 返回值

因为可能会出现字母重复的情况，所以我们不能直接返回所有元素的和，

那我们该怎么去重呢？

相同字符结尾的 dp 值，我们去最大的即可，                

创建一个大小为 26 的数组，里面保存相应字符结尾的最大 dp 值即可。

最后返回数组里的和即可。

3. 代码编写

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 = 0;
        for(auto e : hash) sum += e;
        return sum;
    }
};

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果感到有所收获的话可以给博主点一个赞哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~