문제
- Leetcode 알고리즘 문제
131. Palindrome Partitioning (Medium)- 문제 내용 : [링크]
내가 작성한 코드
class Solution:
def partition(self, s: str) -> List[List[str]]:
def backtrack(k, temp):
if k == len(s):
result.append(temp[:])
return
for i in range(len(s)-k):
w = s[k:k+i+1]
if w == w[::-1]:
temp.append(w)
backtrack(k+i+1, temp)
temp.pop()
result = []
backtrack(0, [])
return result -
주어진 문자열 s를 통해 만들 수 있는 모든 substring을 완전탐색을 통해 찾고, 해당 substring이 palindrome인 경우를 구하는 문제이다.
-
먼저 s를 이용해 만들 수 있는 모든 substring을 구하기 위해
backtrack(k, temp)함수를 구현한다. -
for 반복문에서, k값을 가진 i번째 인덱스일 때, substring을 w 변수에 저장한다.
w = s[k:k+i+1]그리고 반복문의 range를 (len(s)-k)로 설정하여 시작 인덱스가 k만큼 뒤로 가는 로직을 반영해준다. -
이 때, w가 palindrome 일 경우, (즉
if w == w[::-1]:)
temp에 append 해 준다. 이 후, 재귀함수 backtrack을 이용해 그 다음 substring을 구해준다. -
이 때, w가 문자열 s의 k+i+1 직전 인덱스까지의 substring 이므로, backtrack 함수 첫 번째 변수에 k+i+1을 업데이트 해 준다.
-
완전탐색을 반복하면서, backtrack의 k 값이 s의 문자열과 같다면 (즉, s의 substring 다음 인덱스가 없다면)
result에temp를 append 해준 후 return 해 준다. -
backtrack(0 ,[])을 처음 시작으로 완전탐색을 진행한다.
⭐⭐⭐⭐⭐
- palindrome 시간복잡도 =
O(n)/ substring 시간복잡도 =O(2^n)이므로 총 시간복잡도는O(n*2^n)이다.
-
n의 길이 확인결과, 시간복잡도가 크지 않으므로 완전탐색으로 바로 문제 접근
-
palindrome을 확인하는 로직과 substring을 구하는 로직을 반복 숙달해둘 것!(substring은 문자열 중간에 ','를 삽입하는 Case를 구하는 과정을 생각하면 2^n가지를 구할 수 있음)
-
조합, 순열 등의 집합들 리스트(
temp)를 최종 결과(result)에 append 할 때, backtrack 이전에 조건문을 통해 구현해준다.
