131. Palindrome Partitioning

Medium (Trung bình) Python 🔗 Xem trên LeetCode

📋 Đề Bài

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

Example 1:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

Example 2:

Input: s = "a"
Output: [["a"]]

Constraints:

1 <= s.length <= 16
s contains only lowercase English letters.

🧠 Thuật Toán & Kỹ Thuật

Backtracking (Quay lui)

⏱️ Thời gian O(2ⁿ)

💾 Không gian O(n)

💻 Lời Giải

Python 0131-palindrome-partitioning.py

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res = []
        
        def backTracking(s: str, path: List[str]) -> None:
            if not s:
                res.append(path)
                return
            for i in range(1, len(s) + 1):
                if s[:i] == s[:i][::-1]:
                    backTracking(s[i:], path + [s[:i]])
                
        backTracking(s, [])
        
        return res