题目描述
定义字符串 base
为一个 "abcdefghijklmnopqrstuvwxyz"
无限环绕的字符串,所以 base
看起来是这样的:
"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...."
.
给你一个字符串 s
,请你统计并返回 s
中有多少 不同非空子串 也在 base
中出现。
示例 1:
输入:s = "a"
输出:1
解释:字符串 s 的子字符串 "a" 在 base 中出现。
示例 2:
输入:s = "cac"
输出:2
解释:字符串 s 有两个子字符串 ("a", "c") 在 base 中出现。
示例 3:
输入:s = "zab"
输出:6
解释:字符串 s 有六个子字符串 ("z", "a", "b", "za", "ab", and "zab") 在 base 中出现。
提示:
1 <= s.length <= 105
- s 由小写英文字母组成
解法
方法一:动态规划
不妨设 dp[α]
表示 p 中以字符 α 结尾且在 s 中的子串的最大长度,将 dp 求和可以得到最终结果。
时间复杂度 $O(n)$,其中 $n$ 表示字符串 p 的长度。
成为子串的一个标准,需要是连续的,a
与 c
之间少了一个 b
,所以不能算一个子字符串。
1
2
3
4
5
6
7
8
9
10
11
12 | class Solution:
def findSubstringInWraproundString(self, p: str) -> int:
dp = [0] * 26
k = 0
for i, c in enumerate(p):
if i and (ord(c) - ord(p[i - 1])) % 26 == 1:
k += 1
else:
k = 1
idx = ord(c) - ord('a')
dp[idx] = max(dp[idx], k)
return sum(dp)
|
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[] dp = new int[26];
int k = 0;
for (int i = 0; i < p.length(); ++i) {
char c = p.charAt(i);
if (i > 0 && (c - p.charAt(i - 1) + 26) % 26 == 1) {
++k;
} else {
k = 1;
}
dp[c - 'a'] = Math.max(dp[c - 'a'], k);
}
int ans = 0;
for (int v : dp) {
ans += v;
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | class Solution {
public:
int findSubstringInWraproundString(string p) {
vector<int> dp(26);
int k = 0;
for (int i = 0; i < p.size(); ++i) {
char c = p[i];
if (i && (c - p[i - 1] + 26) % 26 == 1)
++k;
else
k = 1;
dp[c - 'a'] = max(dp[c - 'a'], k);
}
int ans = 0;
for (int& v : dp) ans += v;
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | func findSubstringInWraproundString(p string) int {
dp := make([]int, 26)
k := 0
for i := range p {
c := p[i]
if i > 0 && (c-p[i-1]+26)%26 == 1 {
k++
} else {
k = 1
}
dp[c-'a'] = max(dp[c-'a'], k)
}
ans := 0
for _, v := range dp {
ans += v
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | function findSubstringInWraproundString(p: string): number {
const n = p.length;
const dp = new Array(26).fill(0);
let cur = 1;
dp[p.charCodeAt(0) - 'a'.charCodeAt(0)] = 1;
for (let i = 1; i < n; i++) {
if ((p.charCodeAt(i) - p.charCodeAt(i - 1) + 25) % 26 == 0) {
cur++;
} else {
cur = 1;
}
const index = p.charCodeAt(i) - 'a'.charCodeAt(0);
dp[index] = Math.max(dp[index], cur);
}
return dp.reduce((r, v) => r + v);
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | impl Solution {
pub fn find_substring_in_wrapround_string(p: String) -> i32 {
let n = p.len();
let p = p.as_bytes();
let mut dp = [0; 26];
let mut cur = 1;
dp[(p[0] - b'a') as usize] = 1;
for i in 1..n {
if (p[i] - p[i - 1] + 25) % 26 == 0 {
cur += 1;
} else {
cur = 1;
}
let index = (p[i] - b'a') as usize;
dp[index] = dp[index].max(cur);
}
dp.into_iter().sum()
}
}
|