0动态规划中等 LeetCode467. 环绕字符串中唯一的子字符串

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

分析

计算出分别以26个字母为结尾的最长子字符串的长度，加起来就是所有能够在那个无限循环的数组的找到的子字符串的个数。

所有的子串都是以这26个字母为结尾的。分别求出以26个字母为结尾的最长子字符串，就能得到全部的子字符串。

负雪明烛的题解：
本地的思想其实是「滑动窗口」和「动态规划」相结合。
子串相关的动态规划，一般状态的定义都是「以位置 ii 作为结尾的、符合要求的子串长度」。
这样定义，主要是为了简化，因为知道了 dp[i]dp[i]以后，很容易就能得到 dp[i + 1]dp[i+1]。
比如对于本题，我们把状态定义为「pp 中，以位置 ii 作为结尾的、在 ss 中存在的最长子串长度」。
那么在已知了 dp[i]dp[i] 以后，得到 dp[i + 1]dp[i+1] 时，无非两种情况：

当在 ss中， p[i + 1]p[i+1] 是 p[i]p[i] 的下一个字符，那么说明能 连接上，于是 dp[i + 1] = dp[i] + 1dp[i+1]=dp[i]+1。
当在 ss中， p[i + 1]p[i+1] 不是 p[i]p[i] 的下一个字符，那么说明能 连接不上，于是 dp[i + 1] = 1dp[i+1]=1。
作者：fuxuemingzhu
链接：https://leetcode.cn/problems/unique-substrings-in-wraparound-string/solution/by-fuxuemingzhu-ixas/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
    public int findSubstringInWraproundString(String p) {
char[] arr = p.toCharArray();
        int[] dp = new int[26];
        int len = 1;
        dp[arr[0]-'a'] = 1;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] - arr[i-1] == 1 || arr[i] == 'a' && arr[i-1] == 'z') {
                len++;
            } else {
                len = 1;
            }
            if (len > dp[arr[i]-'a']) {
                dp[arr[i]-'a'] = len;
            }
        }
        int ans = 0;
        for (int num : dp) {
            ans += num;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23