[LeetCode] 131. Palindrome Partitioning

131. Palindrome Partitioning

Medium

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

 

Example 1:

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

Example 2:

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

 

Constraints:

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

---

문제 풀이

• 주어진 문장을 가능한 모든 팰린드롬 단어로 나누는 문제이다.
• 알파벳을 연결했을때 팰린드롬이면 합칠 수 있고 나눌 수 도 있다. 
• 제한 사항을 봤을때 최대 길이가 16이기 때문에 완전 탐색인 DFS, BFS로 풀 수 있다. 
• 각 알파벳의 위치 인덱스로 재귀함수를 호출한다. 
• 팰린드롬을 선택하는 기준은 재귀호출 했을때의 시작 위치부터 문자 배열의 마지막 위치까지 탐색한다.
• 현재 위치부터 차례대로 시작 인덱스와 끝 인덱스로 팰린드롬인지 확인한다. 
• 예를 들어 0에서 시작했다면 0부터 문장의 끝길이 까지 확인을 한다.
• 즉 (0, 0), (0, 1), ... (0, 최대길이)까지 확인을 하는데, 확인하는 함수는 시작 좌표와 끝 좌표를 두 인덱스가 만날때까지 줄여나가면서 문자가 같은지 확인한다. 
• 팰린드롬이라면 임시 배열에 넣고 다음 인덱스를 탐색한다. 
• 일반 숫자의 조합을 구하는 방식의 재귀호출을 응요한것이라고 생각할 수 있다. 

소스 코드

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        self.ans = []
        def palin(s, start, end):
            while start < end:
                if s[start] != s[end]: return False
                start += 1
                end -= 1
            return True
        def rec(s, idx, temp):
            if idx >= len(s): self.ans.append(temp.copy())
            for i in range(idx, len(s)):
                if palin(s, idx, i):
                    temp.append(s[idx : i + 1])
                    rec(s, i + 1, temp)
                    temp.pop()
        rec(s, 0, [])
        return self.ans