---
title: "131. Palindrome Partitioning"
url: "https://laigary.com/interview/coding/131-palindrome-partitioning"
type: "note"
section: "coding"
date: "2025-12-01"
updated: "2025-12-01"
tags: ["Palindrome", "Backtrack"]
---

# 131. Palindrome Partitioning

[131\. Palindrome Partitioning](https://leetcode.com/problems/palindrome-partitioning/)

```python
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res = []

        def isPalindrome(start, end):
            left = start
            right = end
            while left < right:
                if s[left] != s[right]:
                    return False
                left += 1
                right -= 1
            return True

        def backtrack(curr, start):
            if start == len(s):
                res.append(list(curr))
                return

            for i in range(start, len(s)):
                if isPalindrome(start, i):
                    curr.append(s[start:i+1])
                    backtrack(curr, i + 1)
                    curr.pop()
        
        backtrack([], 0)

        return res
```

類似題目

-   93 [93\. Restore IP Addresses](/interview/coding/93-restore-ip-addresses)