131. Palindrome Partitioning

题目

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.

Related Topics

字符串

动态规划

回溯

👍 2056

👎 0

思路

本题和回溯排列有些不同，属于回溯子字符串，回溯 check 字段是子字符串 而非 path 元素

解法

# leetcode submit region begin(Prohibit modification and deletion)
from typing import List
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res = []

        def backtrack(start, path):
            if start == len(s):
                res.append(path[:])
                return

            for end in range(start+1, len(s) + 1):
                part = s[start:end]

                if isPalindrome(part):
                    path.append(part)
                    backtrack(end, path)
                    path.pop()




        def isPalindrome(s) -> bool:
            left = 0
            right = len(s)

            while left < right:
                if s[left] == s[right - 1]:
                    left += 1
                    right -= 1
                else:
                    return False

            return True

        backtrack(0,[])
        return  res

# leetcode submit region end(Prohibit modification and deletion)

a = Solution().partition('aab')
print(a)

复杂度分析

• 时间复杂度 O(N * 2^N)
• 空间复杂度 O(N * 2^N)
  • N = len(s)