[리트코드/leetcode/python] 647. Palindromic Substrings

이미지를 누르면 문제 링크를 보실 수 있습니다

해당 문제는 팰린드롬 문제입니다.

'팰린드롬'이라는 것은 문자열을 앞에서 읽나 뒤에서 읽나 동일한 문자열 형태를 띄는 문자열을 말하는데요,

'a'라는 단일문자도 팰린드롬에 속하는 것을 유의하면 됩니다.

 

이 문제에서는 주어진 문자열 s 에 들어있는 팰린드롬 문자열이 총 몇개인지 파악하는 문제입니다.

첫번째 예시에서 문자열 s는 'abc'인데, 각 단일문자만이 팰린드롬이고, 그 외에는 팰린드롬이 아니기에 결과를 3을 리턴합니다.

두번째 예시에서 문자열 s는 'aaa'인데, 결과가 6이 나왔습니다. 

먼저 각 위치에서 'a'가 단일문자로서 팰린드롬을 형성하고, 첫번째,두번째 문자로 이루어진 'aa'와 두번째, 세번째 문자로 이루어진 'aa'가 총 2개 있습니다. 마지막으로 'aaa'도 팰린드롬 문자열이기에 결과적으로 총 팰린드롬 문자열 개수는 6개가 되는 셈입니다.

 

이러한 로직에서 우리가 알 수 있는 것은 앞서 말했듯이, 무조건 '단일문자는 팰린드롬을 형성한다'는 것이고 이러한 전제조건으로부터 시작해야합니다.

 

문자열 s 를 돌면서 각 위치에 해당하는 문자와 그 위치를 기준으로 좌,우를 살피면서 각 문자들이 같은지를 체크하면 됩니다. 

이해가 쉽게 되도록 문자열 'aaaba'라는 문자열로 예시를 들어서 설명해보겠습니다.

현재까지는 팰린드롬의 길이가 홀수인 경우만 체크한 것입니다. yes가 7번 나왔으니 현재까지 7개의 팰린드롬이 있는 것인데요,

위 예시에서 첫번째 문자와 두번째 문자의 결합인 'aa'같은 팰린드롬은 카운트가 되지 않았습니다.

 

팰린드롬의 길이를 1이 아닌 2부터 시작해보면서 각 문자의 왼쪽, 오른쪽으로 살펴보면서 even 케이스도 체크해야만 합니다.

 

이렇게까지 해야 문자열 s 에 포함되어 있는 모든 팰린드롬 substring을 찾을 수 있게 됩니다.

이와 같은 로직을 그대로 코드로 구현하면 아래와 같습니다.

class Solution(object):
    def countSubstrings(self, s):
        answer = 0
        
        for i in range(len(s)):
            left = i
            right = i

            # odd length
            while left >=0 and right < len(s) and s[left]==s[right]:
                answer += 1
                left -= 1
                right += 1


            # even length
            left = i
            right = i + 1
            while left >=0 and right < len(s) and  s[left]==s[right]:
                answer += 1
                left -= 1
                right += 1

        return answer

똑같은 부분이 반복되는 것을 함수화 해서 더 간결하게 코드를 짜면 아래와 같은 코드가 됩니다.

class Solution(object):

    def countSubstrings(self, s):
        
        answer = 0 
        for i in range(len(s)):
            # odd length
            answer += self.countPalindrom(i,i,s)
            # even length
            answer += self.countPalindrom(i,i+1,s)

    
        return answer

    def countPalindrom(self,left,right,s):
    
    	answer = 0
    	while left >=0 and right < len(s) and s[left]==s[right]:
            answer += 1
            left -= 1
            right += 1

        return answer

이렇게 풀면, O(n^3)까지 갈 수 있었던 시간복잡도를 O(n^2)의 시간복잡도로 줄이며 문제를 해결할 수 있게 됩니다. 

이상으로 팰린드롬과 관련한 Palindromic Substrings 문제를 정리해봤습니다.

 

---

[조금 덜 효율적인 투포인터 풀이]

class Solution(object):
    def countSubstrings(self, s):

        n = len(s)
        cnt = 0
        left = 0
        right = 0

        while left <= n-1:
            right = left
            while right < n+1:
                tmp = s[left:right] 
                if tmp and tmp == tmp[::-1]:
                    cnt += 1
                right += 1

            left += 1
        
        return cnt