【dp力扣】环绕字符串中唯一的子字符串

题目链接

题目：

class Solution {
    public int findSubstringInWraproundString(String s) {

    }
}

审题：

给定base这个字符串，它是"abcd……xyz"围成的一个环形无线长度的字符串（只有小写的26个字母）。

在给定一个字符串s，题目要求计算：在s串中的所有的子串（至少包含一个字符）中，有多少个子串在base串中出现过。

示例：

细节注意：

在示例二中，我们要知道重复出现的字符我们只记录一次！！！

尽管'cac'中两个c都存在于base串中，但是只算一个。

状态表示：

dp[i]：
  [i]表示，以[0,i]为范围，i位置为结尾，所有子数组在base串中出现的总次数。

class Solution {
    public int findSubstringInWraproundString(String s) {
         
            
             //把字符串变成字符数组，等一下好操作。
             char[] sArr=s.toCharArray(); 
 
                   int n=sArr.length;


            //dp[i]表示，以[0,i]为范围，i位置为结尾，所有子数组在base串中出现的总次数。
            int[] dp=new int[n];

          
    }
}

通过dp计算正确答案（先讲）

这里我们先不推导状态方程，暂且假设dp数组已经被我们填表完成了。

依据这个dp数组，如何求出答案所需要的子数组出现的总次数呢？

一些童鞋可能会直接说dp数组求和即可。按照经验的确如此，刚开始我也是这样想的。

但，事出反常必有妖。

当前这个问题是解决这个算法的重要环节，所以我放到这里讲。

刚才小编在示例处强调过，重复的字符只能计算一次！所以如果直接对dp求和，那么结果只能是>=正确答案（因为加上了重复的次数）。

比如，s="abdb"，在dp数组中dp[1]dp和dp[3]（dp[i]含义，请看上面代码注释）两个值一定有重复的计数，因为"ab"和"abdb"中都有b这个字符。因此如果是简单的dp求和，结果可能就会比正确答案大。

如何避免重复计数的情况发生呢？（注意下面的内容第一次听可能有点绕，但不难，细心听几遍就懂了）

可以使用哈希的思想避免重复计数。

题目提示说了，s和base一样都是小写的字母，所以定义一个哈希表：

class Solution {
    public int findSubstringInWraproundString(String s) {
         
            
             //把字符串变成字符数组，等一下好操作。
             char[] sArr=s.toCharArray(); 
 
                   int n=sArr.length;


            //dp[i]表示，以[0,i]为范围，i位置为结尾，所有子数组在base串中出现的总次数。
            int[] dp=new int[n];

            这里假定dp数组已经填表完毕了！！



            //确定返回值(用于去重)
            int[] hash=new int[26];

 
    }
}

把dp表映射到hash表中，hash求和就是答案了（映射前hash的每一个元素都是0）。

那么dp表怎么映射到hash表中呢？

实际上，借助字符数组sArr即可：

hash[0]对应的是sArr[i]=='a'

hash[1对应的是sArr[j]=='b'

所以:

hash[0]=sArr[i]

hash[1]=sArr[j]

不过，以上这种模式并没有实现去重。

如果sArr[i]和sArr[j]都等于'b'，怎么办？

这实际上就回到了刚才的"abdb"中，dp[1]和dp[3]出现重复计数的问题了。

其实很简单，直接取最大值：max(dp[1],dp[3])即可。

为什么呢？

dp[i]表示，以[0,i]为范围，i位置为结尾，所有子数组在base串中出现的总次数。

而dp[3]实际上已经包含了子数组dp[1]中的所有情况，

也就是说如果i<j，s[i]==s[j]，那么一定有：dp[i]<dp[j]！（细细理解这句话）

class Solution {
    public int findSubstringInWraproundString(String s) {
         
            
             //把字符串变成字符数组，等一下好操作。
             char[] sArr=s.toCharArray(); 
 
                   int n=sArr.length;


            //dp[i]表示，以[0,i]为范围，i位置为结尾，所有子数组在base串中出现的总次数。
            int[] dp=new int[n];

            这里假定dp数组已经填表完毕了！！

    

            //确定返回值
            int[] hash=new int[26];

                //开始把dp映射到hash（用于去重）
            for(int i=0;i<n;i++){
                hash[sArr[i]-'a']=Math.max(hash[sArr[i]-'a'],dp[i]);
            }

            //hash求和就是答案
            int sum=0;
            for(int h:hash){
                sum+=h;
            }

        return sum;
    }
}

状态方程的初始化以及推导

在回顾以下状态表示dp[i]：[i]表示，以[0,i]为范围，i位置为结尾，所有子数组在base串中出现的总次数。

所以dp[i]和dp[i-1]有什么关系呢？

倘若两个字符s[i]和s[i-1]是连续的，即s[i-1]+1!=s[i]（ASCII码）并且s[i-1]!='z'且s[i]!='a'。那么dp[i]=dp[i-1]+1。(以i为结尾，实际上，也就增加了s[i]这一个字母)

反之，如果不满足粗体条件，dp[i]=1。

如下AC代码：

class Solution {
    public int findSubstringInWraproundString(String s) {
         
            
             //把字符串变成字符数组，等一下好操作。
             char[] sArr=s.toCharArray(); 
 
                   int n=sArr.length;


            //dp[i]表示，以[0,i]为范围，i位置为结尾，所有子数组在base串中出现的总次数。
            int[] dp=new int[n];

            这里假定dp数组已经填表完毕了！！

            dp[0]=1;//涉及i-1，只需要把这个初始化即可！！！！
            for(int i=1;i<n;i++){
                if(sArr[i-1]+1==sArr[i]||(sArr[i-1]=='z'&&sArr[i]=='a')){
                        dp[i]=dp[i-1]+1;
                    }
                else dp[i]=1;
            }

            //确定返回值
            int[] hash=new int[26];

                //开始把dp映射到hash（用于去重）
            for(int i=0;i<n;i++){
                hash[sArr[i]-'a']=Math.max(hash[sArr[i]-'a'],dp[i]);
            }

            //hash求和就是答案
            int sum=0;
            for(int h:hash){
                sum+=h;
            }

        return sum;
    }
}