[Leetcode] 647. Palindromic Substrings (python)

문제

647. Palindromic Substrings

코드

class Solution:
    def countSubstrings(self, s: str) -> int:
        self.slen = len(s)
        self.count = 0
        
        def dfs(l, r):
            if l >= 0 and r < self.slen and s[l] == s[r]:
                self.count += 1
                dfs(l-1, r+1)
                
        for i in range(self.slen):
            dfs(i, i)
            dfs(i, i+1)
            
        return self.count

접근

오랜만에 문제를 푸는 것이라 이전에 풀었던 것을 python으로 다시 풀어보게 되었다. 접근 자체는 brute force 하게 접근하면 되겠다는 생각이 들었고 이를 위해 dfs를 이용하였다. palindrome이라면 길이가 홀수거나 짝수일 수 있지만 필연적으로 맨 앞과 맨 뒤의 값은 같아야 한다. 따라서 범위 값의 유효성을 체크하고 맨 앞과 맨 뒤 값이 동일한지 체크하여 해당하는 경우에 다시 분기를 하게 작성하였다. 좀 더 효율적인 풀이가 있을 것 같다.