Leetcode 131. Palindrome Partitioning

Seawolf

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"]
]

1. class Solution:
   
2.     def partition(self, s: str) -> List[List[str]]:
   
3.         results = []
   
4.         
   
5.         def palindrome(left, right):
   
6.             while left < right:
   
7.                 if s[left] != s[right]:
   
8.                     return False
   
9.                 left += 1
   
10.                 right -= 1
    
11.             return True
    
12.         
    
13.         def dfs(start, result):
    
14.             if start >= len(s):
    
15.                 results.append(result[:])
    
16.                 return
    
17.             
    
18.             for i in range(start, len(s)):
    
19.                 if palindrome(start, i):
    
20.                     result.append(s[start: i + 1])
    
21.                     dfs(i + 1, result)
    
22.                     result.pop(len(result) - 1)
    
23.         
    
24.         dfs(0, [])
    
25.         return results

复制代码