[LeetCode] 131. Palindrome Partitioning_Medium tag: DFS, backtracking, Palindrome

清疚 2021-11-16 07:20 207阅读 0赞

Given a string *s*, partition *s* such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of *s*.

Example:

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

这个题目我们可以理解为是s中不断决定是否要在该character的后面切一刀，可以切，可以不切， 2^n 种可能，让我们想到了subsets[\[LeetCode\] 78. Subsets tag: backtracking][LeetCode_ 78. Subsets tag_ backtracking]，实际上就可以利用subsets的做法，只是temp存储的是s的index， 然后加上每切一刀的时候都要判断是否是palindrome，我们利用[\[Palindrome\] Check any substring in a s is a palindrome or not.][Palindrome_ Check any substring in a s is a palindrome or not.] 来去优化时间复杂度。

T: O(2^n) 因为我们优化了palindrome substring。

Code

class Solution:
        def palindromePartition(self, s):
            ans, palin = [], self.generatePalin(s)
            self.helper(s, [], 0, palin, ans)
            return ans
    
        def generatePalin(self, s):
            n = len(s)
            palin = [[False] * n for  _ in range(n)]
            for i in range(n):
                palin[i][i] = True
                if i and s[i] == s[i - 1]:
                    palin[i - 1][i] = True
            for length in range(2, n):
                for start in range(n):
                    if start + length < n and s[start] == s[start + length]:
                        palin[start][start + length] = palin[start + 1][start + length - 1]
            return palin
        
        def helper(self, s, temp, pos, palin, ans):
            if pos == len(s):
                ans.append(temp)
            for i in range(pos, len(s)):
                if not palin[pos][i]:
                    continue
                self.helper(s, temp + [s[pos: i + 1]], i + 1, palin, ans)

转载于:https://www.cnblogs.com/Johnsonxiong/p/10921504.html

[LeetCode_ 78. Subsets tag_ backtracking]: https://www.cnblogs.com/Johnsonxiong/p/9440473.html
[Palindrome_ Check any substring in a s is a palindrome or not.]: https://www.cnblogs.com/Johnsonxiong/p/10921452.html