[4코3파] #282. Leetcode 647. Palindromic Substrings

[4코3파] 1명의 스위프트 개발자가 도망가고 4명의 코틀린 개발자, 3명의 파이썬 개발자의 코딩 테스트 스터디 : 4코3파

START :

[3코1파] 2023.01.04~ (282일차)
[4코1파] 2023.01.13~ (274일차)
[4코3파] 2023.10.01 ~ (12일차)

Today :

2023.10.12 [282일차]

647. Palindromic Substrings

https://leetcode.com/problems/palindromic-substrings/

문제 설명

문자열 s가 주어질 때, 부분 문자열들 중에서 펠린드롬이 되는 부분 문자열의 개수를 반환함

문제 풀이 방법

brute force로 풀면 시간복잡도가 O(n^3)인데,
문자열을 돌면서 각 인덱스에서 left, right를 비교해가면서 진행하면 O(n*n) = O(n^2)

내 코드

class Solution:
    def countSubstrings(self, s: str) -> int:
        res = 0 
        for i in range(len(s)):
            res += self.countPali(s, i, i)
            res += self.countPali(s,i, i+1)
        return res

    
    def countPali(self, s, l, r):
        res = 0
        while l>=0 and r<len(s) and s[l] == s[r]:
            res +=1
            l-=1
            r+=1
        return res

증빙

여담

어제꺼랑 비슷하네 스위스 기러기 토마토 우영우
사실 왜 left, right i,i로 뒀다가 그 뒤에 right를 i+1로 한 번 더 줘서 도는지 잘 모르겠음 잣.됏.다.