Given a string, your task is to count how many palindromic substrings in this string.
The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.
给定一个字符串，您的任务是计算此字符串中的回文子串数。
具有不同起始索引或结束索引的子字符串被计为不同的子字符串，即使它们由相同的字符组成。
Example 1:
Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".
Example 2:
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
Note:
- The input string length won’t exceed 1000.
python实践
-
蛮力法
出现问题
#!/usr/bin/env python
# _*_ coding:utf-8 _*_
class Solution:
def countSubstrings(self, s):
# 先用最普通的方法来写
if len(s) == 1:
return 1
num = 0
if len(s) < 1000:
if self.judge_pali(s):
num += 1
for win in range(1, len(s)):
for i in range(0, len(s)-win+1):
ss = s[i:i+win]
print(ss)
if self.judge_pali(s[i:i+win]):
num += 1
return num
def judge_pali(self, s):
s = list(s)
s_r = list(reversed(s))
# print(s_r)
for i in range(0, len(s)):
if s[i] == s_r[i]:
continue
else:
break
if i == len(s) - 1:
return True
if __name__ == '__main__':
t = Solution().countSubstrings(s="aaa")
print(t)
