Skip to main content

rustgym/leetcode/
_647_palindromic_substrings.rs

1struct Solution;
2
3impl Solution {
4    fn count_substrings(s: String) -> i32 {
5        let n = s.len();
6        let s: Vec<char> = s.chars().collect();
7        let mut res = 0;
8        let mut dp = vec![vec![false; n + 1]; n + 1];
9        for i in (0..n).rev() {
10            for j in i..n {
11                if j == i
12                    || j == i + 1 && s[i] == s[j]
13                    || j > i + 1 && s[i] == s[j] && dp[i + 1][j - 1]
14                {
15                    dp[i][j] = true;
16                    res += 1;
17                }
18            }
19        }
20        res
21    }
22}
23
24#[test]
25fn test() {
26    let s = "abc".to_string();
27    let res = 3;
28    assert_eq!(Solution::count_substrings(s), res);
29    let s = "aaa".to_string();
30    let res = 6;
31    assert_eq!(Solution::count_substrings(s), res);
32}