Leetcode Python - 647. Palindromic Substrings

Leetcode #647 - Palindromic Substrings

이제 blind 75 leetcode를 풀어보겠습니다. https://leetcode.com/discuss/interview-question/460599/Blind-75-LeetCode-Questions

리트코드의 문제 647 ‘Palindromic Substrings’을 파이썬으로 풀어 보도록 하겠습니다.

이전에 풀었던 5번 문제를 응용하면 쉽게 풀 수 있습니다.

전체 코드는 아래와 같습니다.

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

시간복잡도는

• O(n^2) : 이중루프

공간복잡도는

• O(1) : 상수 변수들 생성