给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

 

示例 1：

输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

输入："aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

 

提示：

    输入的字符串长度不会超过 1000 。

1 fn count_substrings(s: String) -> i32 {
2 let len = s.len();
3 let temp_str = &s as &str;
4 let mut count = 0;
5 for gap in 1..=len {
6 for index in 0..len {
7 if len < index + gap { continue; } 8 let inner_str = &temp_str[index..index+gap]; 9 if is_palindromic(inner_str) { 10 count += 1; 11 } 12 } 13 } 14 count 15 } 16 17 18 fn is_palindromic(substring: &str) -> bool {
19 // let len = substring.len();
20 //
21 // for i in 0..(len / 2) {
22 // let lhs = &substring[i..i + 1];
23 // let rhs = &substring[len - i - 1..len - i];
24 // if lhs.eq(rhs) {
25 // continue;
26 // } else {
27 // return false;
28 // }
29 // }
30 // //遍历完所有正确返回true
31 // true
32
33 let temp = &substring
34 .chars()
35 .rev()
36 .collect::()[..];
37
38 temp == substring
39 }
40
41 fn main() {
42 // let ret = is_palindromic("ab");
43 // aaaaa == 15
44 // aaa == 6
45 // abc == 3
46 let s = String::from("aaaaa"); // 15
47 let ret = count_substrings(s);
48 println!("ret = {}", ret);
49 }

C++ Solution 超时

1 learn string operator
2 1. 截取子串
3 s.substr(pos, n) 截取s中从pos开始（包括0）的n个字符的子串，并返回
4 s.substr(pos) 截取s中从从pos开始（包括0）到末尾的所有字符的子串，并返回
5 2. 替换子串
6 s.replace(pos, n, s1) 用s1替换s中从pos开始（包括0）的n个字符的子串
7 3. 查找子串
8 s.find(s1) 查找s中第一次出现s1的位置，并返回（包括0）
9 s.rfind(s1) 查找s中最后次出现s1的位置，并返回（包括0）
10 s.find_first_of(s1) 查找在s1中任意一个字符在s中第一次出现的位置，并返回（包括0）
11 s.find_last_of(s1) 查找在s1中任意一个字符在s中最后一次出现的位置，并返回（包括0）
12 s.fin_first_not_of(s1) 查找s中第一个不属于s1中的字符的位置，并返回（包括0）
13 s.fin_last_not_of(s1) 查找s中最后一个不属于s1中的字符的位置，并返回（包括0）
14 * */
15
16
17
18 #include
19 #include
20 #include
21
22 using namespace std;
23 bool is_palindromic(string s);
24
25 int countSubstrings(string s) {
26 int length = s.length();
27 // cout << "length = " << length << endl;
28 int count = 0;
29 for (int gap = 1; gap <= length; gap++){
30 for (int index = 0; index < length; index++){
31 if (length < index + gap) {
32 continue;
33 }
34 string inner_str = s.substr(index, gap);
35 // cout << "inner_str = " << inner_str << endl;
36 if (is_palindromic(inner_str)) {
37 count += 1;
38 }
39 }
40 }
41 return count;
42 }
43
44 bool is_palindromic(string s) {
45 int length = s.length();
46 for (int i = 0; i < length/2; i++){
47 string lhs = s.substr(i,1);
48 string rhs = s.substr(length-i-1,1);
49 if (lhs == rhs) {
50 continue;
51 }else {
52 return false;
53 }
54 }
55 return true;
56 }
57
58
59 int main() {
60 string s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
61
62 int ret = countSubstrings(s);
63 // bool ret = is_palindromic(s);
64 cout << "ret = " << ret << endl;
65 return 0;
66 }

Python Soluton 超时

1 # 代码超时
2 #
3 #
4 # python string slice
5 #
6 # 切片操作（slice）可以从一个字符串中获取子字符串（字符串的一部分）。我们使用一对方括号、起始偏移量start、终止偏移量end 以及可选的步长step 来定义一个分片。
7 #
8 # 格式： [start🔚step]
9 #
10 # • [:] 提取从开头（默认位置0）到结尾（默认位置-1）的整个字符串
11 # • [start:] 从start 提取到结尾
12 # • [:end] 从开头提取到end - 1
13 # • [start:end] 从start 提取到end - 1
14 # • [start🔚step] 从start 提取到end - 1，每step 个字符提取一个
15 # • 左侧第一个字符的位置/偏移量为0，右侧最后一个字符的位置/偏移量为-1
16 #
17 #
18 #
19 # 几个特别的examples 如下：
20 #
21 # 提取最后N个字符：
22 #
23 # >>> letter = 'abcdefghijklmnopqrstuvwxyz'
24 # >>> letter[-3:]
25 # 'xyz'
26 #
27 # 从开头到结尾，step为N：
28 #
29 # >>> letter[::5]
30 # 'afkpuz'
31 #
32 # 将字符串倒转(reverse)， 通过设置步长为负数：
33 #
34 # >>> letter[::-1]
35 # 'zyxwvutsrqponmlkjihgfedcba'
36
37
38
39 def is_palindromic(s: str) -> bool:
40 length: int = len(s)
41 for i in range(length // 2):
42 lhs = s[i:i + 1]
43 rhs = s[length - i - 1:length - i]
44 if lhs == rhs:
45 continue
46 else:
47 return False
48 return True
49
50
51 def countSubstrings(s: str) -> int:
52 # def is_palindromic(s: str) -> bool:
53 # _length: int = len(s)
54 # for i in range(_length // 2):
55 # lhs = s[i:i + 1]
56 # rhs = s[_length - i - 1:_length - i]
57 # if lhs == rhs:
58 # continue
59 # else:
60 # return False
61 # return True
62
63 length: int = len(s)
64 count = 0
65 for gap in range(length):
66 new_gap = gap + 1
67 for index in range(length):
68 if length < index + new_gap:
69 continue
70 inner_str = s[index:index + new_gap]
71 if is_palindromic(inner_str):
72 count += 1
73
74 return count
75
76
77 if __name__ == "__main__":
78 # print("is_palindromic {}".format(is_palindromic("abc")))
79
80 print("ret = {}".format(countSubstrings("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa")))

Github Link: https://github.com/DaviRain-Su/leetcode_solution/tree/master/palindromic_substrings