动态规划 —— 子数组系列-环绕字符串中唯⼀的子字符串

1. 环绕字符串中唯⼀的子字符串

题目链接：

467. 环绕字符串中唯一的子字符串 - 力扣（LeetCode）https://leetcode.cn/problems/unique-substrings-in-wraparound-string/description/

 2. 题目解析

示例2

示例3 

3. 算法原理 

状态表示：以某一个位置为结尾或者以某一个位置为起点

  

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

  

2. 状态转移方程

  

  

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 + dp[i-1] 

3. 初始化 ：把dp表填满不越界，让后面的填表可以顺利进行

  

我们可以把数组里的值全部初始化为1（这个1是长度），这样的话上面的状态转移方程就可以改为dp[i] += dp[i-1] 

4. 填表顺序 

  

本题的填表顺序是：从左往右

5. 返回值 ：题目要求 + 状态表示     

    

本题不能直接返回dp表里所有元素的和，以示例2为例：{c,a,c}初始化为1之后返回的是3，但是应该返回2才对，因为重复计算了一次c，所有我们应该先进行去重

  

  

本题的返回值是：

  

4.  代码

动态规划的固定四步骤：1.  创建一个dp表

                                        2. 在填表之前初始化

                                        3. 填表（填表方法：状态转移方程）

                                        4. 确定返回值

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']=0
            hash[s[i]-'a']=max( hash[s[i]-'a'],dp[i]);//保存相应字符结尾的最大值

        int sum=0;
        for(auto x:hash) sum+=x;

        return sum;
    }
};

 子数组系列的问题就到此为止啦，完结撒花~