LeetCode 131(Palindrome Partitioning, Python)

1. 문제 링크

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

LeetCode - The World's Leading Online Programming Learning Platform

2. 문제 설명

• 문자열 s가 주어졌을 때, 모든 substring이 palindrome하도록 s를 partition하라.
  • 여기서 palindrome이란, 문자열을 거꾸로 해도, 기존 문자열과 동일한 문자열을 의미한다.
    • ex. wow는 뒤집어도 wow다.
• 예제1) s = "aab"라면, output은 [["a","a","b"], ["aa","b"]]가 된다.
• 예제2) s = "a"라면, output은 [["a"]]가 된다. 

3. 처음 풀이 

• backtracker를 사용하여 dfs를 해결하는 것이 어느정도 유형화 된 느낌이다.
• 해당 문제도 backtracker를 활용하였고,
  • path와 start를 argument로 한 함수 helper에 대해
  • start포인트가 len(s)에 도달하면, 지금까지의 path를 output에 append하여 반환하고, 
  • 그 외의 경우에는,
    • range(start, len(s))에 대하여,
      • substring이 뒤집어도 동일한지 (substring == substring[::-1])를 체크하여,
      • 동일하다면 path에 append하고, 
      • helper를 호출, 다시 path를 pop하는 방식으로 코드를 작성하였다. 
  • runtime은 70%정도 나왔다. 

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        
        output = []
        lenth_s = len(s)
        
        def helper(path,start):
            if start == lenth_s:
                output.append(path[:])
                return 

            for i in range(start, len(s)):
                substring = s[start:i+1]
                if substring == substring[::-1]: 
                    path.append(substring)
                    helper(path,i+1)
                    path.pop()

        helper([],0)

        return output

 

5. 배운 점

• slicing은 heavy한 연산이니, 아래처럼 하는 것보다, variable에 사용하는것이 낫다.
  • 최대한 중복 계산을 피하기 위해 변수에 저장하는 것을 고려하자.

  if s[start:i+1] == s[start:i+1][::-1]: 
    path.append(s[start:i+1])
    helper(path,i+1)
    path.pop()

• path.copy()보다 path[:]를 사용하는게 runtime관점에서 좋다.