-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy patha7VOhD.rs
43 lines (35 loc) · 1.07 KB
/
a7VOhD.rs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#![allow(dead_code, unused, unused_variables, non_snake_case)]
fn main() {
assert_eq!(Solution::count_substrings("abc".into()), 3);
assert_eq!(Solution::count_substrings("aaa".into()), 6);
}
struct Solution;
impl Solution {
/// dp[i][j] = bool, 表示子串s[i..j] 是否为回文字符串
/// - dp[i+1][j-1] && s[i] == s[j], j - i > 1
/// -
/// dp[i][j]
/// -
/// - s[i] == s[j], j-i==1
///
pub fn count_substrings(s: String) -> i32 {
let mut dp = vec![vec![false; s.len()]; s.len()];
let mut ans = 0;
let mut len = 0;
let s = s.as_bytes();
while len <= s.len() {
for i in 0..s.len() - len {
if len <= 1 {
dp[i][i + len] = s[i] == s[i + len];
} else {
dp[i][i + len] = s[i] == s[i + len] && dp[i + 1][i + len - 1];
}
if dp[i][i + len] {
ans += 1;
}
}
len += 1;
}
ans
}
}