Leetcode 131. Palindrome Partitioning - Python

Leetcode 131 문제 보기

 

문제 이해하기

알파벳 소문자로 이루어진 String s에 대하여 파티션을 나누었을 때, 각각의 substring들이 팰린드롬일 경우의 파티션들을 출력하라.

팰린드롬이란, 순서를 뒤집어도 본래의 단어와 같은 단어를 의미한다.

 

아이디어 구상

Decision Tree를 그리며 생각해보자.

주어진 단어 s를 root로 시작해서, 가능한 s의 substring들을 그려나간다.

탐색 시, 만약 s의 substring이 팰린드롬이 아니라면 해당 경우에 대한 탐색을 멈춘다. (Backtracking)

 

s = "aab" 일 경우의 test case를 살펴보자.

By Mesotes

 

탐색을 진행하며 "ab" 와 "aab"의 경우, 각각의 substring이 팰린드롬이 아니므로 탐색을 중단하게 된다.

따라서 본 test case의 경우, ["a", "a", "b"] 와 ["aa", "b"], 총 두 가지 경우를 출력할 수 있게 된다.

 

이 때의 시간복잡도는 어떻게 될까?

len(s) == n이라 했을 때, 최대 (2 ^ n)개의 substring이 발생한다.

이 때 각각의 substring을 생성하고 팰린드롬 여부를 판별하기 위해 substring 당 O(n)의 연산이 필요하다.

따라서 최악의 경우 Time Complexity ~ O(n * (2 ^ n)) 가 예상된다.

 

풀이

정답을 담을 리스트 res와 탐색 과정에서 substring들을 담을 리스트 part를 선언한다.

res = []
part = []

 

dfs()의 base case는 다음과 같다.

substring들을 만들며 index가 len(s)에 도달했을 경우, 탐색을 중단하고 part를 res에 copy한다.

여기서 주의할 점은, part를 그대로 res에 담아서는 안된다는 것이다.

 

그대로 append하지 않고 copy를 하는 이유는 앞선 포스팅에서 설명한 바 있다.

Leetcode 46. Permutations 풀이-base case 참조

if i == len(s):
    res.append(part[:])
    return

 

dfs()의 재귀 부분은 다음과 같다.

아이디어 구상에서 살펴봤듯이, index i와 j를 이용해 가능한 substring들을 part에 담는다.

이 때, substring이 팰린드롬일 경우, 즉, isPali()가 True일 때만 탐색을 이어나가도록 한다.

for j in range(i, len(s)):
    if isPali(i, j):
        part.append(s[i:j + 1])
        dfs(j + 1)
        part.pop()

 

isPali() 함수는 다음과 같이 투 포인터를 이용하여 쉽게 구현할 수 있다.

맨 앞과 맨 뒤의 글자가 다를 경우 False를 return하고 그렇지 않을 경우 한단계 범위를 좁혀 탐색을 진행하도록 한다.

모든 글자에 대해 탐색을 진행할 때까지 False가 아니었다면 해당 단어는 팰린드롬이다.

def isPali(left, right):
    while left < right:
        if s[left] != s[right]:
            return False
        left, right = left + 1, right - 1
    return True

 

전체 코드는 다음과 같다.

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res = []
        part = []
        
        
        def isPali(left, right):
            while left < right:
                if s[left] != s[right]:
                    return False
                left, right = left + 1, right - 1
            return True
        
        
        def dfs(i):
            # base case
            if i == len(s):
                res.append(part[:])
                return
            
            for j in range(i, len(s)):
                if isPali(i, j):
                    part.append(s[i:j + 1])
                    dfs(j + 1)
                    part.pop()
                    
        dfs(0)
        return res

 

---

Leetcode 131. Palindrome Partitioning

https://leetcode.com/problems/palindrome-partitioning/​

 

 

 

 

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

 

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

 

 

 

 

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

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