Palindrome Partitioning
Welcome to Day 39 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore the Palindrome Partitioning problem, which combines string manipulation with dynamic programming concepts.
What is Palindrome Partitioning?
Palindrome Partitioning is the problem of dividing a string into substrings, where each substring is a palindrome. A palindrome is a string that reads the same backward as forward.
Problem Statement
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
Naive Recursive Approach
Let’s start with a naive recursive implementation:
1def is_palindrome(s, start, end):
2 while start < end:
3 if s[start] != s[end]:
4 return False
5 start += 1
6 end -= 1
7 return True
8
9def palindrome_partition_recursive(s):
10 def backtrack(start, path):
11 if start == len(s):
12 result.append(path[:])
13 return
14
15 for end in range(start, len(s)):
16 if is_palindrome(s, start, end):
17 path.append(s[start: …
Palindrome Partitioning
Welcome to Day 39 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore the Palindrome Partitioning problem, which combines string manipulation with dynamic programming concepts.
What is Palindrome Partitioning?
Palindrome Partitioning is the problem of dividing a string into substrings, where each substring is a palindrome. A palindrome is a string that reads the same backward as forward.
Problem Statement
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
Naive Recursive Approach
Let’s start with a naive recursive implementation:
1def is_palindrome(s, start, end):
2 while start < end:
3 if s[start] != s[end]:
4 return False
5 start += 1
6 end -= 1
7 return True
8
9def palindrome_partition_recursive(s):
10 def backtrack(start, path):
11 if start == len(s):
12 result.append(path[:])
13 return
14
15 for end in range(start, len(s)):
16 if is_palindrome(s, start, end):
17 path.append(s[start:end+1])
18 backtrack(end + 1, path)
19 path.pop()
20
21 result = []
22 backtrack(0, [])
23 return result
24
25# Example usage
26s = "aab"
27print(f"Palindrome partitions of '{s}': {palindrome_partition_recursive(s)}")
This approach has a time complexity of O(n * 2^n), where n is the length of the string, making it inefficient for longer strings.
Dynamic Programming Approach
We can improve the efficiency using Dynamic Programming to precompute palindrome information.
1def palindrome_partition_dp(s):
2 n = len(s)
3 # dp[i][j] is True if s[i:j+1] is a palindrome
4 dp = [[False] * n for _ in range(n)]
5
6 # All substrings of length 1 are palindromes
7 for i in range(n):
8 dp[i][i] = True
9
10 # Check for substrings of length 2 and more
11 for length in range(2, n + 1):
12 for i in range(n - length + 1):
13 j = i + length - 1
14 if length == 2:
15 dp[i][j] = (s[i] == s[j])
16 else:
17 dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]
18
19 def backtrack(start, path):
20 if start == n:
21 result.append(path[:])
22 return
23
24 for end in range(start, n):
25 if dp[start][end]:
26 path.append(s[start:end+1])
27 backtrack(end + 1, path)
28 path.pop()
29
30 result = []
31 backtrack(0, [])
32 return result
33
34# Example usage
35s = "aab"
36print(f"Palindrome partitions of '{s}': {palindrome_partition_dp(s)}")
This approach has a time complexity of O(n * 2^n) in the worst case, but it’s generally faster due to the precomputation of palindrome information.
Optimized Solution: Manacher’s Algorithm
For very long strings, we can use Manacher’s Algorithm to find all palindromic substrings in O(n) time, which can then be used to optimize our partitioning:
1def manacher(s):
2 t = '#' + '#'.join(s) + '#'
3 n = len(t)
4 p = [0] * n
5 c = r = 0
6 for i in range(1, n-1):
7 mirror = 2*c - i
8 if i < r:
9 p[i] = min(r - i, p[mirror])
10 while i + (1 + p[i]) < n and i - (1 + p[i]) >= 0 and t[i + (1 + p[i])] == t[i - (1 + p[i])]:
11 p[i] += 1
12 if i + p[i] > r:
13 c, r = i, i + p[i]
14 return p
15
16def palindrome_partition_manacher(s):
17 p = manacher(s)
18 n = len(s)
19 is_palindrome = [[False] * n for _ in range(n)]
20 for i in range(n):
21 for j in range(i, n):
22 center = i + j + 1
23 radius = j - i
24 if p[center] >= radius:
25 is_palindrome[i][j] = True
26
27 def backtrack(start, path):
28 if start == n:
29 result.append(path[:])
30 return
31
32 for end in range(start, n):
33 if is_palindrome[start][end]:
34 path.append(s[start:end+1])
35 backtrack(end + 1, path)
36 path.pop()
37
38 result = []
39 backtrack(0, [])
40 return result
41
42# Example usage
43s = "aab"
44print(f"Palindrome partitions of '{s}': {palindrome_partition_manacher(s)}")
This approach has a time complexity of O(n) for palindrome precomputation and O(2^n) for partitioning in the worst case.
Applications of Palindrome Partitioning
- Text processing and analysis
- Bioinformatics (DNA sequence analysis)
- Natural Language Processing
- Cryptography and steganography
Exercise
Modify the algorithm to find the minimum number of cuts needed to partition a string into palindromes.
Implement a function that finds the longest palindromic subsequence in a string using dynamic programming.
Create an algorithm that generates all possible palindromes that can be formed by rearranging the characters of a given string.
Summary
Today, we explored the Palindrome Partitioning problem, which combines string manipulation with dynamic programming concepts. We implemented various approaches, from naive recursion to optimized solutions using Manacher’s Algorithm.
Understanding Palindrome Partitioning and its solutions provides valuable insights into string manipulation techniques and their applications in various fields of computer science.
Tomorrow, we’ll dive into another interesting problem: the Longest Palindromic Substring. Stay tuned!