leetcode : Palindrome Partitioning

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

Palindrome Partitioning - LeetCode

 

어제 dp문제 풀고 정신 나가서 dp연습이나 해야겠다 하고 Dynamic Programming 카테고리에서 찾아들어간 문젠데 Backtracking문제였다 ㅋㅋㅋㅋ.. 정답을 빨리 안봤으면 큰일날뻔

 

급하게 보느라 constraints를 안봤는데 봤으면 백트래킹인거 바로 알았을듯. 역시 사람은 꼼꼼해야 된다.

근데 그렇다고 dp를 적용 못하는건 아니다. substring palindrome 체크하는거에 dp를 적용하면 속도가 매우 빨라짐

 

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        
        dp = [[None]*17 for _ in range(17)]
        
        def dfs(i, path, result):
            if i == len(s):
                result.append(path[:])
                return
                
            for j in range(i + 1, len(s) + 1):
                if isPal(i, j):
                    dfs(j, path + [s[i:j]], result)
                
        def isPal(i, j):
            if dp[i][j] != None:
                return dp[i][j]
            else:
                dp[i][j] = s[i:j] == s[i:j][::-1]
                return dp[i][j]
        
        result = []
        dfs(0, [], result)
        return result