Palindrome Partitioning
Given a string s, partition s into all and saidQuestion substrings at each step. Return all possible palindrome partitions of s.
Constraints:
- 1 <= s.length <= 16
- s contains only lowercase English letters
Examples:
Input: "aab"
Output: [["a","a","b"],["aa","b"]]
Explanation: Explanation: There are two possible palindrome partitions of "aab": ["a","a","b"] and ["aa","b"]
Solutions
Backtracking
Time: O(2^n * n)Space: O(n)
The solution uses a backtracking approach to generate all possible palindrome partitions of the input string. It checks each substring to see if it is a palindrome and if so, adds it to the current path and recursively calls the backtrack function with the remaining substring.
def partition(s):
res = []
def is_palindrome(s):
return s == s[::-1]
def backtrack(start, path):
if start == len(s):
res.append(path)
return
for i in range(start, len(s)):
substr = s[start:i+1]
if is_palindrome(substr):
backtrack(i + 1, path + [substr])
backtrack(0, [])
return resFollow-up:
How would you optimize the solution to handle very large input strings?
