【算法】【动规】环绕字符串中唯一的子字符串

跳转汇总链接

👉🔗动态规划算法汇总链接

1.5 环绕字符串中的子字符串

🔗题目链接

定义字符串 base 为一个 “abcdefghijklmnopqrstuvwxyz” 无限环绕的字符串，所以 base 看起来是这样的：

"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

给你一个字符串 s ，请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。

1. 状态表示
   • 本题依旧以 s 字符串上 i 位置为结尾作为一个状态。
   • dp[i] 表示以 i 位置为结尾的字符串有多少个子数组，在 base 中出现过。
2. 状态转移方程

   • 看官方示例，明显能进行划分的状态查找方式就是：i 位置自身、i 位置自身+之前的子数组

     dp[i] 可以分成两种情况考虑，
     	if 长度为1，1
     	if 长度大于1，&& s[i-1] 和 s[i] 是连接的，dp[i-1]
     	             && s[i-1] 和 s[i] 不连接，0
     dp[i] = 两种情况的总和
     

3. 初始化
   • dp 表都初始化为 1，长度为 1 的情况就不用考虑了。
4. 填表顺序
   • 从左往右依次填写。
5. 返回值
   • 题目中的 “不同” 子串，需要我们提供一个去重的策略，分析后很容易得出一个结论，以相同字符结尾的字符串，其 dp 值大的一定会包含 dp 值小的那个，所以我们只需要取 dp 值大的那个就可以了！去重逻辑如下（重复+无序+字母字符，用数组元素和对应下标储存很方便~）：
     • 创建一个大小为 26 的数组；
     • 里面保存相应字符结尾的最大 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] - s[i-1] == 1) || (s[i] == 'a' && s[i-1] == 'z'))
                dp[i] += dp[i-1];

        // 这里注意，需要再遍历一次，把上面落下的第一个数据算进来
        int ret[26] = {0};
        for(int i = 0; i < n; i++)
            ret[s[i]-'a'] = max(ret[s[i]-'a'], dp[i]);

        int sum = 0;
        for(auto e: ret) sum += e;

        return sum;
    }
};

🥰如果本文对你有些帮助，欢迎👉 点赞 收藏 关注，你的支持是对作者大大莫大的鼓励！！(????) 若有差错恳请留言指正~~