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

Difficulty
Medium
Tags
动态规划
URL
https://leetcode.cn/problems/unique-substrings-in-wraparound-string/
Star
把字符串 s 看作 "abcdefghijklmnopqrstuvwxyz" 的无限环绕字符串，所以 s 看起来是这样的：
  • "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...." 。
现在给定另一个字符串 p 。返回 s 中 不同 的 p 的 非空子串 的数量 。
示例 1：
输入：p = "a"
输出：1
解释：字符串 s 中只有 p 的一个 "a" 子字符。
示例 2：
输入：p = "cac"
输出：2
解释：字符串 s 中只有 p 的两个子串 ("a", "c") 。
示例 3：
输入：p = "zab"
输出：6
解释：在字符串 s 中有 p 的六个子串 ("z", "a", "b", "za", "ab", "zab") 。
提示：
  • 1 <= p.length <= 105
  • p 由小写英文字母组成
通过次数34,004提交次数65,715

法1 动态规划

思路
计算个数的，最后只保留次数最多的！求一个数组的连续子数组总个数：以索引为 0 结尾的子数组个数 + 以索引为 1 结尾的子数组个数 + ... + 以索引为 n - 1 结尾的子数组个数，这无疑是完备的。
题解
class Solution:
    def findSubstringInWraproundString(self, p: str) -> int:
        dp = [1 for _ in p]

        h = collections.defaultdict(int)
        h[p[0]] = 1
        for i in range(1, len(p)):
            if ord(p[i]) - ord(p[i-1]) == 1 or (p[i] == "a" and p[i-1] == "z"):
                dp[i] = dp[i-1] + 1
            h[p[i]] = max(h[p[i]], dp[i])
  
        return sum(h.values())