## 题目描述：

LeetCode 647. Palindromic Substrings

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:

1. The input string length won't exceed 1000.

## 解题思路：

```初始化空队列queue

将队首弹出，记为(left, right)，将计数器+1

若(left - 1, right + 1)索引范围有效，并且s[left - 1] == s[right + 1]，将其加入queue```

## Python代码：

``````class Solution(object):
def countSubstrings(self, s):
"""
:type s: str
:rtype: int
"""
size = len(s)
queue = collections.deque((x, x) for x in range(size))
for x in range(size - 1):
if s[x] == s[x + 1]:
queue.append((x, x + 1))
ans = 0
while queue:
x, y = queue.popleft()
ans += 1
if x - 1 >= 0 and y + 1 < size and s[x - 1] == s[y + 1]:
queue.append((x - 1, y + 1))
return ans
``````

Pingbacks已关闭。

1. 书影网友 发布于 2017年7月30日 02:27 #

认真进行了学习。