[Leetcode 131] - Palindrome Partitioning w/ Python

 

Given a string s, partition s such that every substring of the partition is a palindrome . 

Return all possible palindrome partitioning of s.

 

 

s라는 string이 주어졌을때 글자를 분할해서 회문이 되는 모든 경우를 찾는 문제

 

 

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

 

 

---

 

 

 

Example 1:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

 

 

 

Example 2:

Input: s = "a"
Output: [["a"]]

 

 

 

---

 

 

 

 

백트래킹으로 해결 가능한 문제

 

모든 글자에서 시작해 각각 다음에 오는 글자를 합쳐서 palindrome이라면 stack에 먼저 저장

끝까지 도달했을때 ans에 저장해서 한 글자로 시작된 부분에서 panlindrome인것을 저장

 

 

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        ans = []
        stack = []

        def backtrack(left):
            if left >= len(s):
                ans.append(stack.copy())
                return
            for right in range(left, len(s)):
                if self.check(s, left, right):
                    stack.append(s[left:right+1])
                    backtrack(right + 1)
                    stack.pop()
        
            return
        
        backtrack(0)
        return ans
    
    def check(self, s, l, r):
        while l < r:
            if s[l] != s[r]:
                return False
            l, r = l + 1, r - 1
        return True