LeetCode #131. Palindrome Partitioning 해설

해설

 

준비과정

• 팰린드롬은 거꾸로 해도 같은 문자열을 의미한다.
• 팰린드롬의 리스트를 저장하기 위한 공간 self.path 를 준비한다.
• 결과를 담을 공간 self.result 를 준비한다.

백트래킹이 끝나는 조건 (종결조건) 정하기.

• 백트래킹의 종결 조건은 startIndex가 문자열 s의 길이와 같을 경우, 즉 모든 인덱스를 둘러봤을 때로 정한다.
• 그리고 종결 조건을 만족하게 되면 self.path를 self.result에 넣고 return하여 해당 함수를 끝낸다.

백트래킹 알고리즘 정하기.

• startIndex부터 s라는 문자열의 끝까지 for루프를 통해 횡방향 탐색을 진행한다.
• 만약 팰린드롬 조건(s[startIndex:i+1] == s[startIndex:i+1][::-1])을 만족하게 되면 self.path에 해당 문자열을 넣고, 더 나아가 i+1부터 시작하는 백트래킹을 돌린다.
• 백트래킹이 끝나는 지점에선 self.path.pop()을 통해 마지막 요소를 제거해준다.

 

알고리즘도

 

 

코드

 

from typing import List

class Solution:
    def __init__(self):
        self.path = []
        self.result = []

    def partition(self, s: str) -> List[List[str]]:
        self.backtracking(s, 0)
        return self.result
    
    def backtracking(self, s, startIndex):
    	# 종결 조건 - Terminate Condition (startIndex가 s의 마지막 index 초과할 경우)
        if startIndex == len(s):
            self.result.append(self.path[:])
            return
        
        for i in range(startIndex, len(s)):
        	# 거꾸로 해도 같을 경우 (팰린드롬) path 리스트에 넣는다.
            if (s[startIndex:i+1] == s[startIndex:i+1][::-1]):
                self.path.append(s[startIndex:i+1])
                self.backtracking(s, i+1) # 종방향 backtracking 진행
                self.path.pop()


if __name__ == '__main__':
    sol = Solution()
    sol.partition("aab")