1.题目基本信息

1.1.题目描述

定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串，所以 base 看起来是这样的：

• "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

给你一个字符串 s ，请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。

1.2.题目地址

https://leetcode.cn/problems/unique-substrings-in-wraparound-string/description/

2.解题方法

2.1.解题思路

动态规划。在字符串base中，只要知道子串的结尾字符和长度，就能确定一个子串；为了找到s中有多少个不同的非空子串在base中出现，只需找以各个不同字符结尾的最长匹配子串的长度即可，然后各个最长长度的和即为题解

2.2.解题步骤

第一步，状态定义。dp[\alpha]为s中以字符\alpha结尾的最长匹配子串的长度

第二步，状态初始化。dp[s[0]]=1

第三步，状态转移。dp[\alpha]=max(dp[\alpha],dp[\alpha-1]+1)。使用length维护以当前的s[i]结尾的最长子串的长度

第四步，sum(dp)即为题解

3.解题代码

python3代码

class Solution:
    def findSubstringInWraproundString(self, s: str) -> int:
        # 思路：动态规划。在字符串base中，只要知道子串的结尾字符和长度，就能确定一个子串；为了找到s中有多少个不同的非空子串在base中出现，只需找以各个不同字符结尾的最长匹配子串的长度即可，然后各个最长长度的和即为题解
        n = len(s)
        # 第一步，状态定义。dp[\alpha]为s中以字符\alpha结尾的最长匹配子串的长度
        dp = [0] * 26
        # 第二步，状态初始化。dp[s[0]]=1
        dp[ord(s[0]) - ord('a')] = 1
        # 第三步，状态转移。dp[\alpha]=max(dp[\alpha],dp[\alpha-1]+1)。使用length维护以当前的s[i]结尾的最长子串的长度
        length = 1
        for i in range(1, n):
            index = ord(s[i]) - ord('a')
            if index == (ord(s[i - 1]) - ord('a') + 1) % 26:
                length += 1
                dp[index] = max(dp[index], length)
            else:
                length = 1
                dp[index] = max(dp[index], 1)
        # 第四步，sum(dp)即为题解
        return sum(dp)

4.执行结果