-
Notifications
You must be signed in to change notification settings - Fork 0
/
q2 Smallest Palindrome.py
97 lines (84 loc) · 2.36 KB
/
q2 Smallest Palindrome.py
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
# -*- coding: utf-8 -*-
"""
Created on Sat Nov 2 23:07:46 2019
@author: Satvik Chachra
"""
# =============================================================================
#
# Programming Assignment-2: Smallest Palindrome
# Due on 2019-10-24, 23:59 IST
# Given a string S having characters from English alphabets ['a' - 'z'] and '.' as the special character (without quotes).
# Write a program to construct the lexicographically smallest palindrome by filling each of the faded character ('.') with a lower case alphabet.
#
# Definition:
# The smallest lexicographical order is an order relation where string s is smaller than t, given the first character of s (s1 ) is smaller than the first character of t (t1 ), or in case they
# are equivalent, the second character, etc.
#
# For example "aaabbb" is smaller than "aaac" because although the first three characters
# are equal, the fourth character b is smaller than the fourth character c.
#
# Input Format:
# String S
#
# Output Format:
# Print lexicographically smallest palindrome after filling each '.' character, if it
# possible to construct one. Print -1 otherwise.
#
# Example-1
#
# Input:
# a.ba
#
# Output:
# abba
#
#
# Example-2:
#
# Input:
# a.b
#
# Output:
# -1
#
# Explanation:
# In example 1, you can create a palindrome by filling the '.' character by 'b'.
# In example 2, it is not possible to make the string s a palindrome.
#
# =============================================================================
import string
ip = input()
lst = list(ip)
rlst = lst[::-1]
alpha = list(string.ascii_lowercase)
dot = '.'
def check_pal(lst,rlst):
if(lst == rlst):
return 1
else:
return 0
def place_alpha(lst,rlst,alphabet):
idx1 = None
idx2 = None
for i in range(len(lst)):
if (dot == lst[i]):
lst[i] = alphabet
idx1 = i
for j in range(len(rlst)):
if (dot == rlst[j]):
rlst[j] = alphabet
idx2 = j
value = check_pal(lst,rlst)
if(value==1):
return 1
else:
lst[idx1] = '.'
rlst[idx2] = '.'
return 0
for x in range(0,len(alpha)):
val = place_alpha(lst,rlst,alpha[x])
if(val==1):
print(lst)
break
else:
print(-1)