Problem link
https://leetcode.com/problems/palindromic-substrings
Problem Summary
문자열이 주어질 때 palindrome인 substring의 개수를 구하는 문제.
Solution
처음 보면 좀 어려워 보이는데 팰린드롬 체크를 좌 우로 한 칸씩 늘려가면서 체크하는 방식으로 생각하면 쉽게 풀린다.
즉, s[left : right] 가 팰린드롬일 때 s[left - 1] == s[right + 1]이면 s[left - 1 : right + 1]도 팰린드롬이다.
for 문을 돌면서 홀수 개수, 짝수 개수 하면서 현재 위치 기준으로 좌우로 체크하면 된다. 시간복잡도는 O(n^2)
Source Code
class Solution:
def countSubstrings(self, s: str) -> int:
res = 0
# odd length
for i in range(len(s)):
l = r = i
while l >= 0 and r < len(s) and s[l] == s[r]:
res += 1
l -= 1
r += 1
# even length
for i in range(len(s)):
l, r = i, i + 1
while l >= 0 and r < len(s) and s[l] == s[r]:
res += 1
l -= 1
r += 1
return res