647. Palindromic Substrings
Đề Bài
Given a string s, return the number of palindromic substrings in it.
A string is a palindrome when it reads the same backward as forward.
A substring is a contiguous sequence of characters within the string.
Example 1:
Input: s = "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c".
Example 2:
Input: s = "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
Constraints:
1 <= s.length <= 1000sconsists of lowercase English letters.
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(n)
💾 Không gian
O(1)
Lời Giải
Python
0647-palindromic-substrings.py
class Solution:
def __init__(self):
self.n = 0
def helper(self, s, i, j):
cnt = 0
while i >= 0 and j < self.n and s[i] == s[j]:
i -= 1
j += 1
cnt += 1
return cnt
def countSubstrings(self, s: str) -> int:
self.n = len(s)
ans = 0
for i in range(self.n):
ans += self.helper(s, i, i)
ans += self.helper(s, i, i + 1)
return ans