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

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; } };

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