LeetCode——467.环绕字符串中唯一的子字符串

大佬，牛！！！

• 就是给你一个字母串s，是按照26个应为字母无限循环的。然后再给你一个p，问一下这个p中有多少个s的子字符串。
• 我的思路：我们可以发现，如果我知道子串的长度n，那么n中有n*(n+1)/2个子串（其实就是1+…+n），都满足是s的子串。这里举个例子哈，如果p是zbcdeg，那么bcd是一个子串对吧，并且bcd中还有b、c、d、bc、cd也都是，一共有6个，bcd的长度是n=3，所以一共有34/2个。但是这里就存在一个问题，怎么去重。就是如果还有一个abcd呢，这时候n是4，然后个数为45/2是10，但是与bcd肯定是有重复的啊，那怎么办？我就是没想好这个去重怎么办，只要能去重，其实我们找到每个最长的子串，然后分别进行计算即可。我就是卡在去重上上面了。
• 大佬的思路：大佬用到了动态规划 。关于“分别求到以26个字母为结尾的最长子串的长度之和，就是最终的结果”，这个很关键，我用一个举例的方式给大家演示，还是bcd的问题，这时候是1+2+3，然后如果出现一个abcd呢？这时候是1+2+3+4，并且这里面包含了1+2+3，然后我们就可以发现了，其实我只要针对d结尾，保留这个4就可以了，然后针对c结尾的保留3，以此类推即可。而这个4就是以d为结尾的最长子串的长度。
• 技巧：动态规划，关键——分别求到以26个字母为结尾的最长子串的长度之和，就是最终的结果

java代码

class Solution {
    public int findSubstringInWraproundString(String p) {
        // 分别求到以26个字母为结尾的最长子串的长度之和，就是最终的结果
        int[] dp = new int[26];
        int ret = 0, num = 0;
        char c;
        for (int i = 0; i < p.length(); i++) {
            c = p.charAt(i);
            if (i > 0 && (c - p.charAt(i - 1) == 1 || p.charAt(i - 1) - c == 25)) {// 构成字串
                num++;
            } else {
                num = 1;
            }
            // 更新以i位置结尾的字符串，要取最大值
            dp[p.charAt(i) - 'a'] = Math.max(dp[p.charAt(i) - 'a'], num);
        }
        for (int t : dp) {
            ret += t;
        }
        return ret;
    }
}

• 总结：其实动态规划的问题就是遮掩，如果你知道发现了其中的规律，就会变得非常简单。最后附上大佬的链接。