blob: 7d037bdc0db2badcf413f28731437753ae583a23 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
#!/usr/bin/env python3
# Challenge 065
#
# TASK #2 > Palindrome Partition
# Submitted by: Mohammad S Anwar
# Reviewed by: Ryan Thompson
#
# You are given a string $S. Write a script print all possible partitions that
# gives Palindrome. Return -1 if none found.
#
# Please make sure, partition should not overlap. For example, for given string
# "abaab", the partition "aba" and "baab" would not be valid, since they overlap.
#
# Example 1
# Input: $S = 'aabaab'
# Ouput:
# There are 3 possible solutions.
# a) 'aabaa'
# b) 'aa', 'baab'
# c) 'aba'
# Example 2
# Input: $S = 'abbaba'
# Output:
# There are 3 possible solutions.
# a) 'abba'
# b) 'bb', 'aba'
# c) 'bab'
import sys
def is_palindrome(s):
return len(s) >= 2 and s == s[::-1]
def partitions(s):
seen = set()
length = len(s)
for lead in range(length + 1):
for p1 in range(2, length + 1):
for p2 in [0] + list(range(2, length + 1)):
for tail in range(length + 1):
if lead + p1 + p2 + tail != length:
continue
s1 = s[lead:lead+p1]
s2 = s[lead+p1:lead+p1+p2]
if is_palindrome(s1) and is_palindrome(s2):
key = f"{s1}, {s2}"
if key not in seen:
print(key)
seen.add(key)
elif is_palindrome(s1):
if s1 not in seen:
print(s1)
seen.add(s1)
partitions(sys.argv[1] if len(sys.argv) > 1 else "")
|
