CODEWITHSUNDEEP
pythonstringpalindrome
Endi
Endi

Reputation: 11

how to make an imputed string to a list, change it to a palindrome(if it isn't already) and reverse it as a string back

A string is palindrome if it reads the same forward and backward. Given a string that contains only lower case English alphabets, you are required to create a new palindrome string from the given string following the rules gives below: 1. You can reduce (but not increase) any character in a string by one; for example you can reduce the character h to g but not from g to h 2. In order to achieve your goal, if you have to then you can reduce a character of a string repeatedly until it becomes the letter a; but once it becomes a, you cannot reduce it any further. Each reduction operation is counted as one. So you need to count as well how many reductions you make. Write a Python program that reads a string from a user input (using raw_input statement), creates a palindrome string from the given string with the minimum possible number of operations and then prints the palindrome string created and the number of operations needed to create the new palindrome string.

I tried to convert the string to a list first, then modify the list so that should any string be given, if its not a palindrome, it automatically edits it to a palindrome and then prints the result.after modifying the list, convert it back to a string.

c=raw_input("enter a string ") 
x=list(c) 
y = "" 
i = 0 
j = len(x)-1 
a = 0 
while i < j:
        if x[i] < x[j]:
            a += ord(x[j]) - ord(x[i])
            x[j] = x[i]
            print x

        else:
            a += ord(x[i]) - ord(x[j])
            x [i] = x[j]
            print x

        i = i + 1
        j = (len(x)-1)-1
         print "The number of operations is ",a print "The palindrome created is",( ''.join(x) )

Am i approaching it the right way or is there something I'm not adding up?

Upvotes: 1

Views: 842

Answers (2)

SREYASHI SAHA
SREYASHI SAHA

Reputation: 11

Since only reduction is allowed, it is clear that the number of reductions for each pair will be the difference between them. For example, consider the string 'abcd'.

Here the pairs to check are (a,d) and (b,c). Now difference between 'a' and 'd' is 3, which is obtained by (ord('d')-ord('a')). I am using absolute value to avoid checking which alphabet has higher ASCII value.

I hope this approach will help.

  s=input()
  l=len(s)

  count=0  
  m=0
  n=l-1
  
  while m<n:
    count+=abs(ord(s[m])-ord(s[n]))
    m+=1
    n-=1
  
  print(count)

Upvotes: 1

WGS
WGS

Reputation: 14179

This is a common "homework" or competition question. The basic concept here is that you have to find a way to get to minimum values with as few reduction operations as possible. The trick here is to utilize string manipulation to keep that number low. For this particular problem, there are two very simple things to remember: 1) you have to split the string, and 2) you have to apply a bit of symmetry.

First, split the string in half. The following function should do it.

def split_string_to_halves(string):

    half, rem = divmod(len(string), 2)
    a, b, c = '', '', ''
    a, b = string[:half], string[half:]
    if rem > 0:
        b, c = string[half + 1:], string[rem + 1]
    return (a, b, c)

The above should recreate the string if you do a + c + b. Next is you have to convert a and b to lists and map the ord function on each half. Leave the remainder alone, if any.

def convert_to_ord_list(string):
    return map(ord, list(string))

Since you just have to do a one-way operation (only reduction, no need for addition), you can assume that for each pair of elements in the two converted lists, the higher value less the lower value is the number of operations needed. Easier shown than said:

def convert_to_palindrome(string):

    halfone, halftwo, rem = split_string_to_halves(string)

    if halfone == halftwo[::-1]:
        return halfone + halftwo + rem, 0

    halftwo = halftwo[::-1]

    zipped = zip(convert_to_ord_list(halfone), convert_to_ord_list(halftwo))

    counter = sum([max(x) - min(x) for x in zipped])
    floors = [min(x) for x in zipped]
    res = "".join(map(chr, floors))
    res += rem + res[::-1]

    return res, counter

Finally, some tests:

target = 'ideal'
print convert_to_palindrome(target) # ('iaeai', 6)

target = 'euler'
print convert_to_palindrome(target) # ('eelee', 29)

target = 'ohmygodthisisinsane'
print convert_to_palindrome(target) # ('ehasgidihmhidigsahe', 84)

I'm not sure if this is optimized nor if I covered all bases. But I think this pretty much covers the general concept of the approach needed. Compared to your code, this is clearer and actually works (yours does not). Good luck and let us know how this works for you.

Upvotes: 0

Related Questions