647. Palindromic Substrings

[zeikar]

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