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

发表于 分类于 ， 阅读次数： Waline： 本文字数： 1.1k 阅读时长 ≈ 1 分钟

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

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

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

示例：

输入: p = "a"

输出: 1

解释: 字符串 s 中只有一个"a"子字符。

输入: p = "cac"

输出: 2

解释: 字符串 s 中的字符串“cac”只有两个子串“a”、“c”。.

输入: p = "zab"

输出: 6

解释: 在字符串 s 中有六个子串“z”、“a”、“b”、“za”、“ab”、“zab”。

思路：

线性dp，dp[i] 是以 p[i]为结尾的最大有效子串长度 如果p[i] - p[i - 1] == 1或p[i] == 'a' && p[i - 1] == 'z',则dp[i] = dp[i - 1] + 1 否则只能自己组成子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findSubstringInWraproundString(string p) {
        int mp[26] = {0};
        int n = p.size();
        vector<int> dp(n, 1);
        mp[p[0] - 'a'] = 1;
        for(int i = 1; i < n; i++){
            if(p[i] - p[i - 1] == 1 || p[i] == 'a' && p[i - 1] == 'z'){
                dp[i] = dp[i - 1] + 1;
            }
            mp[p[i] - 'a'] = max(mp[p[i] - 'a'], dp[i]);
        }
        int res = 0;
        for(int i = 0; i < 26; i++){
            res += mp[i];
        }
        return res;
    }
};