[LeetCode] 131 | Palindrome Partitioning | Python

---

문제 링크: https://leetcode.com/problems/palindrome-partitioning/

---

문제

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

A palindrome string is a string that reads the same backward as forward.

---

조건

• 1 <= s.length <= 16
• s contains only lowercase English letters.

---

내 풀이

palindrome인지 확인하는 is_palindrome함수를 만든다.

is_palindrome을 이용해 주어진 string 안의 모든 palindrome을 확인해서 배열(self.pal)에 따로 저장한다. (partition 함수 안의 이중 for문)

 

self.pal은 2차원 배열이며, string이 다음과 같이 주어질 때 이런 식으로 생성된다.

self.pal[i][j]는 s[i:j]가 palindrome이라는 뜻이다.

s = 'aabaa'
self.pal = [[1,2,5], [2, 4], [3], [4, 5], [5]]]

 

Recursive하게 돌면서(split 함수) self.pal을 차례로 넣으면 된다.

---

코드

class Solution:
    def partition(self, s: str):
        N = len(s)
        self.ans = []
        self.s = s
        self.pal = [[] for _ in range(N)]
        
        for n in range(N):
            for i in range(N-n):
                temp = s[i:i+n+1]
                if self.is_palindrome(temp):
                    self.pal[i].append(i+n+1)
        
        self.split([], [], 0)
        return self.ans
    
    def split(self, Nans, check, start):
        for end in self.pal[start]:
            if start == 0:
                Nans, check = [], []
            if start in check:
                idx = check.index(start)
                Nans = Nans[:idx+1]
                check = check[:idx+1]

            Nans.append(self.s[start:end])
            check.append(end)
            if end == len(self.s):
                self.ans.append(Nans)
            else:
                self.split(Nans, check, end)
        
                
    def is_palindrome(self, word):
        hN = int(len(word)/2)
        
        for n in range(hN):
            if word[n] != word[len(word)-n-1]:
                return False
        
        return True