目录
题目要求
思路：动态规划
- 遍历
p
p
p寻找其中存在的各种
s
s
s的子串，定义数组
d
p
dp
dp存放子串的长度：
-
d
p
[
i
]
dp[i]
dp[i]指以当前字符为结尾且存在于
s
s
s中的子串的最长长度；
- 事实上这个子串长度刚好等于这个子串拥有的更小的子串的数量（以当前字符为结尾）；
- 比如当前
p
p
p为『……vabc……』
- ……
- 遍历到a时，（dp[a]=）
d
p
[
0
]
=
1
dp[0]=1
dp[0]=1，它所拥有的子串包括“a”，共
1
1
1个；
- 遍历到b时，（dp[b]=）
d
p
[
1
]
=
2
dp[1]=2
dp[1]=2，它所拥有的子串包括“b”、“ab”，共
2
2
2个；
- 遍历到c时，（dp[c]=）
d
p
[
2
]
=
3
dp[2]=3
dp[2]=3，它所拥有的子串包括“c”、“bc”、“abc”，共
3
3
3个；
- ……
- 最后只需要把所有的
d
p
dp
dp内容加起来就好了。
Java
class Solution {
public int findSubstringInWraproundString(String p) {
int[] dp = new int [26];
int len = 0;
for(int i = 0; i < p.length(); ++i) {
if(i > 0 && (p.charAt(i) - p.charAt(i - 1) + 26) % 26 == 1) // 两字符相邻
len++;
else
len = 1;
dp[p.charAt(i) - 'a'] = Math.max(dp[p.charAt(i) - 'a'], len); // 更新最长长度
}
return Arrays.stream(dp).sum(); // 累加所有长度
}
}
- 时间复杂度：
O
(
n
)
O(n)
O(n)，其中
n
n
n为字符串
p
p
p的长度
- 空间复杂度：
O
(
∣
Σ
∣
)
O(|Σ|)
O(∣Σ∣)，取决于字符集大小、其实就是个常数复杂度，对本题来讲就是26个小写字母
C++
class Solution {
public:
int findSubstringInWraproundString(string p) {
vector dp(26);
int len = 0;
for(int i = 0; i < p.length(); ++i) {
if(i > 0 && (p[i] - p[i - 1] + 26) % 26 == 1) // 两字符相邻
len++;
else
len = 1;
dp[p[i] - 'a'] = max(dp[p[i] - 'a'], len); // 更新最长长度
}
return accumulate(dp.begin(), dp.end(), 0);
}
};
- 时间复杂度：
O
(
n
)
O(n)
O(n)
- 空间复杂度：
O
(
∣
Σ
∣
)
O(|Σ|)
O(∣Σ∣)，取决于字符集大小、其实就是个常数复杂度，对本题来讲就是26个小写字母
Rust
impl Solution {
pub fn find_substring_in_wrapround_string(p: String) -> i32 {
let mut dp = vec![0;26];
let mut len = 0;
let pab = p.as_bytes();
for i in 0..p.len() {
if i > 0 && (pab[i] - pab[i - 1] + 26) % 26 == 1 { // 两字符相邻
len += 1;
}
else {
len = 1;
}
dp[(pab[i] - b'a') as usize] = dp[(pab[i] - b'a') as usize].max(len); // 更新最长长度
}
dp.iter().sum() // 累加所有长度
}
}
- 时间复杂度：
O
(
n
)
O(n)
O(n)
- 空间复杂度：
O
(
∣
Σ
∣
)
O(|Σ|)
O(∣Σ∣)，取决于字符集大小、其实就是个常数复杂度，对本题来讲就是26个小写字母
总结
一个平平无奇动态规划中等题，三叶姐姐一个树状数组给我整懵了、大材小用了属于是，感觉反而兜了一圈，不如定义一个临时的
l
e
n
len
len。
