Backtracking: 131. Palindrome Partitioning

131. Palindrome Partitioning

 

https://youtu.be/3jvWodd7ht0?si=paC9K4J8hqA0IgZJ

 

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        # palindrome: 앞으로 읽으나 뒤로 읽으나 같은 문자열을 의미

        res = []  # 모든 가능한 회문 분할 결과를 저장할 리스트

        # 주어진 문자열이 palindrome인지 확인하는 함수
        def isPalidrome(substring):
            # 문자열을 뒤집어서 비교하여 palindrome 여부 반환
            return substring == substring[::-1]

        # 백트래킹 함수
        def backtrack(subset, idx):
            # 기저 조건: idx가 문자열의 끝에 도달했을 때
            if idx >= len(s):
                # 현재까지의 부분집합(subset)을 결과(res)에 추가
                res.append(subset.copy())
                return

            # idx부터 문자열의 가능한 끝점을 탐색
            for j in range(idx, len(s)):
                # s[idx:j+1]이 palindrome인지 확인
                # if isPalidrome(s[idx:j+1]):
                if self.isPal(s, idx, j):
                    # palindrome인 경우 subset에 추가
                    subset.append(s[idx:j+1])
                    # 다음 인덱스부터 탐색
                    backtrack(subset, j+1)
                    # 탐색이 끝난 후 상태를 복구 (백트래킹)
                    subset.pop()

        # 백트래킹 시작 (빈 부분집합과 첫 번째 인덱스부터 탐색 시작)
        backtrack([], 0)

        return res

    # 두 인덱스(l, r) 사이의 문자열이 palindrome인지 확인하는 함수
    def isPal(self, s, l, r):
        # 양쪽에서 가운데로 이동하며 문자열 비교
        while l < r:
            # 서로 다른 문자가 발견되면 False 반환
            if s[l] != s[r]:
                return False
            # 인덱스 업데이트
            l, r = l + 1, r - 1
        # 모두 확인 후 회문이면 True 반환
        return True