leetcode.com 131. Palindrome Partitioning

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

파이썬 소스: https://bit.ly/3VQtynw

 

문제 풀이를 하기에 앞서서, palindrome의 의미를 먼저 알아야 합니다. 어떤 스트링 s가 있을 때, 그 스트링을 앞으로부터 읽은 글자와, 뒤부터 읽은 글자가 같은 경우에, 해당 스트링을 palindrome하다고 합니다.

‘a’ 왼쪽에서 오른쪽으로 읽은값 a, 오른쪽에서 왼쪽으로 읽은 값 a 따라서, palindrome하다.

‘aa’ 왼쪽에서 오른쪽, aa, 오른쪽에서 왼쪽 aa, 따라서, palindrome합니다.

‘ab’ 왼쪽에서 오른쪽 ab, 오른쪽에서 왼쪽, ba, 따라서 ab != ba 임으로, palindrome하지 않습니다.

‘aba’는 palindrome합니다.

‘abcba’도 palindrome합니다.

‘aaccaa’도 palindrome합니다.

 

그러면, 스트링 s가 주어졌을 때, palindrome 인지 확인하는 메서드부터 코딩해 보겠습니다. 주의할 점은 길이가 1인 스트링도 palindrome한 것으로 판단해야 합니다.

def is_palindrome(self, s):     idx_left, idx_right = 0, len(s) - 1     while (idx_left <= idx_right):         if s[idx_left] == s[idx_right]:             idx_left += 1             idx_right -= 1             continue         else:             return False     return True

 

투포인터 알고리즘에서, idx_left, idx_right 2개의 포인터를 사용하는 것처럼, 스트링의 왼쪽 끝과 오른쪽 끝을 가리키는 2개의 인덱스를 만들어 줍니다.

변수 idx_left, idx_right는 s의 길이가 홀 수 인 경우에, while를 나오기 전에 서로 값이 같을 때까지 진행합니다. 따라서, idx_left <= idx_right 로 구현되어 있는 것을 확인하세요.

이제 스트링 s의 각 문자를 비교 하구요, s[idx_left]와 s[idx_right]를 비교해서, 같으면 idx_left를 오른쪽으로 한 칸 이동하고, idx_right를 왼쪽으로 한 칸 이동합니다.

while루프를 마치면, palindrome한 스트링임으로, True를 리턴합니다.

 

 문제의 정의를 잘 확인해야 할 부분은 스트링 s를 잘라서(partition) 만들어지는 모든 substring들이 palindrome한 상태여야 합니다. backtracking기법으로 재귀함수를 호출해 갈 때 마다, 만들어지는 substring은 항상 palindrome한 상태여야 합니다.

 

 이문제를 backtracking으로 풀이하는 방법을 Example 1번을 사용해서 알아보겠습니다.

s = aab 인 상태로 시작합니다.

첫번째 재귀함수 a가 palindrome합니다. 첫번째 a를 s에서 때어내서, s = ab가 됩니다.

두번째 재귀함수 a가 palindrome합니다. 두번째 a를 때어내서, s = b

세번째 재귀함수 b가 palindrome합니다. s = ‘’ 이기 때문에, 세번째 지귀함수까지 오는 동안 모아둔, [a, a, b]를 answer에 넣어 준다음, 두번째 재귀로 리턴합니다.

두번째 재귀, 두번째 a + b는 palindrome이 아닙니다. 멈춰서, 첫번째 재귀로 돌아 갑니다.

첫번째 재귀, 첫번째 a + 두번째 a는 palindrome합니다. s = b가 됩니다.

두번째 재귀, b 는 palindrome합니다. s = ‘’ 이기 때문에, 두번째 재귀함수까지 오는 동안 모아둔 [aa, b]를 answer에 넣어준 다음, 첫번째 재귀함수로 리턴합니다.

첫번째 재귀함수, 첫번째 a + 두번째 a + b 는 palindrome이 아닙니다. 멈춰서 리턴합니다.

 

 위의 방법으로 이 문제를 코딩한 코드는 아래와 같습니다.

from typing import List class Solution:     def partition(self, s: str) -> List[List[str]]:         answer = []         self.bt(s, 0, [], answer)         return answer     def bt(self, rest, idx_left, pathes, answer):         if len(rest) == 0:             answer.append(pathes)             return         for idx_right in range(idx_left, len(rest)):             part = rest[idx_left:idx_right + 1]             if self.is_palindrome(part):                 self.bt(rest[idx_right + 1:], 0, pathes + [part], answer)     def is_palindrome(self, s):         idx_left, idx_right = 0, len(s) - 1         while (idx_left <= idx_right):             if s[idx_left] == s[idx_right]:                 idx_left += 1                 idx_right -= 1                 continue             else:                 return False         return True

 

코데풀 유튜브 구독 부탁드립니다.

https://www.youtube.com/@codapul