【leetcode刷题】T84-回文子串
【题目】
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。
示例 :
输入: "abc"
输出:
解释: 三个回文子串: "a", "b", "c".
示例 :
输入: "aaa"
输出:
说明: 个回文子串: "a", "a", "a", "aa", "aa", "aaa".
注意:
输入的字符串长度不会超过1000。
【思路】
回文串的定义是：字符串的正序和逆序相同。
暴力破解：得到所有子串，判断其是否为回文数。时间复杂度非常高。
在优化解法前，最好明白【T59-最长回文子串】的解法。
对于回文串，有"bab"和"baab"两种模式，第一种模式只有一个中心，第二种模式有两个中心。
我们遍历每个元素，以该元素s[i]为中心找到所有回文串，再以s[i]和s[i+1]为双中心找到所有回文串。进行计数即可得到答案。
【代码】
python版本
class Solution(object):
def countSubstrings(self, s):
"""
:type s: str
:rtype: int
"""
length = len(s)
# 单字符都是回文字符串
count = length
for i in range(length):
# s[i]为回文串唯一中心
for j in range(, length):
if i-j >= and i+j < length and s[i-j] == s[i+j]:
count +=
else:
break
# s[i]和s[i+1]为回文串双中心
for j in range(, length):
if i+-j >= and i+j < length and s[i+-j] == s[i+j]:
count +=
else:
break
return count
C++版本
class Solution {
public:
int countSubstrings(string s) {
int length = s.size();
// 所有单字符都是回文串
int count = length;
for(int i=; i<length; i++){
//s[i]为回文串唯一中心
for(int j=; j<length; j++){
if(i-j >= && i+j < length && s[i-j] == s[i+j])
count++;
else
break;
}
//s[i]和s[i+1]为回文串双中心
for(int j=; j<length; j++){
if(i+-j >= && i+j < length && s[i+-j] == s[i+j])
count++;
else
break;
}
}
return count;
}
};本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-06-07，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读