侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【动态规划】环绕字符串中唯一的子字符串

GabrielxD
2022-05-26 / 0 评论 / 0 点赞 / 31 阅读 / 695 字 / 正在检测是否收录...

题目

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


把字符串 s 看作是 “abcdefghijklmnopqrstuvwxyz” 的无限环绕字符串,所以 s 看起来是这样的:

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

现在给定另一个字符串 p 。返回 s 中 唯一 的 p 的 非空子串 的数量 。

示例 1:

输入: p = "a"
输出: 1
解释: 字符串 s 中只有一个"a"子字符。

示例 2:

输入: p = "cac"
输出: 2
解释: 字符串 s 中的字符串“cac”只有两个子串“a”、“c”。.

示例 3:

输入: p = "zab"
输出: 6
解释: 在字符串 s 中有六个子串“z”、“a”、“b”、“za”、“ab”、“zab”。

提示:

  • 1 <= p.length <= 10^5
  • p 由小写英文字母构成

解题

方法一:动态规划

思路

由于 s 是周期字符串,对于在 s 中的子串,只要知道子串的第一个字符(或最后一个字符)和子串长度,就能确定这个子串。例如子串以 'd' 结尾,长度为 3,那么该子串为 "bcd"
题目要求不同的子串个数,那么对于两个以同一个字符结尾的子串,长的那个子串必然包含短的那个。
例如 "abcd""bcd" 均以 'd' 结尾,"bcd""abcd" 的子串。

知道了上面的规律,就可以定义一个动态规划数组(dp),其中 dp[α] 表示 p 中以字符 α 结尾且在 s 中的字串的最长长度,知道了最长长度,也就知道了不同的子串的个数。
接下来,遍历 p 并维护一个连续递增字串长度 subLen,对于遍历到的每个 i

  • 如果 p[i]p[i-1]s (也就是循环字母表)中的下一个字母,则将 subLen++
  • 否则,将 subLen 重置为 1,表示重新开始计算连续递增的字串长度。
  • 然后用 subLen 更新 dp[p[i]] 的最大值。

遍历完成后,p 中以字符 β 结尾且在 s 中的字串有 dp[β] 个。例如:dp['d'] 表示字串 "bcd""cd""d"。所以答案就是 dp 中所有元素之和。

代码

class Solution {
    public int findSubstringInWraproundString(String p) {
        char[] charArr = p.toCharArray();
        int[] dp = new int[26];
        dp[charArr[0] - 'a']++;
        for (int i = 1, subLen = 1; i < charArr.length; i++) {
            int curr = charArr[i] - 'a', prev = charArr[i - 1] - 'a';
            if ((curr - prev + 26) % 26 == 1) subLen++;
            else subLen = 1;
            dp[curr] = Math.max(dp[curr], subLen);
        }
        int ans = 0;
        for (int cnt : dp) ans += cnt;
        return ans;
    }
}
0

评论区