파이썬(Python)에서 문자열 내 회문 부분 문자열 개수 구하는 프로그램

문자열 s가 주어졌을 때, 해당 문자열 안에 존재하는 회문(palindrome) 부분 문자열의 개수를 구하는 것이 목표입니다.

예를 들어 입력 문자열이 s = "level"이라면 출력은 7이 됩니다. 회문 부분 문자열이 ["l", "e", "v", "e", "l", "eve", "level"]로 총 7개이기 때문입니다.

문제 해결 접근 방식

이 문제는 각 인덱스를 중심으로 삼아 양쪽으로 확장해 가며 회문 여부를 확인하는 방식으로 효율적으로 해결할 수 있습니다.

구체적인 알고리즘은 다음과 같습니다.

• check_palindrome() 함수를 정의합니다. 이 함수는 문자열과 left, right 두 인덱스를 매개변수로 받습니다.
• ans := 0 으로 초기화합니다.
• left ≥ 0 이고 right가 문자열 길이보다 작은 동안 다음을 반복합니다.
  • s[left]와 s[right]가 같다면 → ans를 1 증가시키고, left는 1 감소, right는 1 증가시켜 더 넓은 범위를 확인합니다.
  • 두 문자가 다르다면 → 지금까지 센 ans 값을 그대로 반환합니다.
• 반복이 끝나면 ans를 반환합니다.

메인 로직에서는 다음 과정을 수행합니다.

• ans := 0 으로 초기화합니다.
• 모든 인덱스 char_index에 대해 다음 두 가지 경우를 검사합니다.
  • 홀수 길이 회문: check_palindrome(s, char_index - 1, char_index + 1)
  • 짝수 길이 회문: check_palindrome(s, char_index, char_index + 1)
• 마지막으로 ans + len(s)를 반환합니다. 길이가 1인 부분 문자열은 모두 회문이므로 문자열 길이만큼 더해주는 것입니다.

아래 예제 코드를 통해 더 자세히 살펴보겠습니다.

예제 코드

class Solution:
    def solve(self, s):
        def check_palindrome(string, left, right):
            ans = 0
            while left >= 0 and right < len(s):
                if s[left] == s[right]:
                    ans += 1
                    left -= 1
                    right += 1
                else:
                    return ans
            return ans
        ans = 0
        for char_index in range(len(s)):
            ans += check_palindrome(s, char_index - 1, char_index + 1)
            ans += check_palindrome(s, char_index, char_index + 1)
        return ans + len(s)

ob = Solution()
print(ob.solve("level"))

입력

"level"

출력

7

복잡도 분석

이 알고리즘의 시간 복잡도는 O(n²)이며, 별도의 추가 메모리 없이 수행되므로 공간 복잡도는 O(1)입니다. 여기서 n은 문자열의 길이를 의미합니다.