Leetcode 647. Palindromic Substrings - Python

Leetcode 647 문제 보기

 

문제 이해하기

영문 알파벳 소문자로 이루어진 문자열 s가 주어진다.

이때 s의 substring 중 팰린드롬인 경우가 얼마나 되는지 구하여라.

 

아이디어 구상

substring, 즉 부분문자열은 문자열내에서 일부 문자열을 그대로 떼어낸 형태를 말한다.

팰린드롬이란 앞뒤가 똑같은, 뒤집혀도 뒤집히기 전과 형태가 같은 것을 의미한다.

 

각각의 substring이 팰린드롬인지 확인하기 위해서는 어떤 한 character를 중심으로 양 옆으로 포인터가 퍼지며 두 포인터가 가리키는 character가 같은지 확인하면 된다.

그렇다면 for문을 통해 문자열 s의 첫번째 글자부터 반복을 돌리고, 각 글자에 대해 중심부터 투 포인터가 퍼지며 팰린드롬 여부를 판별하면 되겠다.

 

by Mesotes

 

여기서 하나 자그마한 문제는, substring이 홀수일 때와 짝수일 때를 center의 개수가 달라진다는 점이다.

홀수일 경우, center는 하나의 글자가 되지만, 짝수일 경우 center를 두 글자로 해야한다.

 

풀이

팰린드롬인 substring의 개수를 담을 res를 선언한다.

res = 0

 

주어진 문자열 s에 대하여 루프를 돌린다.

for i in range(len(s)):
	# find palindromic substrings

 

팰린드롬인 부분문자열을 찾는 알고리즘을 설계한다.

투 포인터가 center 글자를 기준으로 퍼져나가며 만약 팰린드롬일 경우 res의 개수를 1씩 증가시킨다.

홀수일 경우 글자 하나, 짝수일 경우 두 개의 글자를 center로 한다.

left, right = i, i
while left >= 0 and right < len(s) and s[left] == s[right]:
    res += 1
    left -= 1
    right += 1
            
left, right = i, i + 1
while left >= 0 and right < len(s) and s[left] == s[right]:
    res += 1
    left -= 1
    right += 1

 

전체 코드는 다음과 같다.

class Solution:
    def countSubstrings(self, s: str) -> int:
        res = 0
        
        for i in range(len(s)):
            left, right = i, i
            while left >= 0 and right < len(s) and s[left] == s[right]:
                res += 1
                left -= 1
                right += 1
            
            left, right = i, i + 1
            while left >= 0 and right < len(s) and s[left] == s[right]:
                res += 1
                left -= 1
                right += 1
        
        return res

---

 

Leetcode 647. Palindromic Substrings

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

​

 

 

 

-문제해결흐름을 간단히 정리한 주관적 포스팅-

 

-부족한 설명이 있다면 부디 조언 부탁드립니다-

 

 

 

 

이 포스팅은 쿠팡 파트너스 활동의 일환으로,

이에 따른 일정액의 수수료를 제공받습니다