This is a question on algorithms. Please read and answer carefully. Thank you. G
ID: 3602141 • Letter: T
Question
This is a question on algorithms. Please read and answer carefully. Thank you.
Given any string of only lowercase letters ’a’ through ’z’ with exactly two of each letter present (for instance, “aabb” or “acbebaec”) develop an algorithm to transform it into a palindrome (for instance, “abba” or “cbaeeabc”) using the minimum number of the following moves.
(a) The only move available is: send a letter to the end of the string.
(b) The only two moves available are:
i) one round of bubble sort (a single iteration, not until sorted).
ii) transpose a pair of adjacent letters.
Explanation / Answer
""" below is the python code for this"""
"""
1. sort it using bubble sort.
2. move every second character from end to last
"""
def bubbleSort(input_string):
input_string = list(input_string)
for passnum in range(len(input_string)-1,0,-1):
for i in range(passnum):
if input_string[i]>input_string[i+1]:
temp = input_string[i]
input_string[i] = input_string[i+1]
input_string[i+1] = temp
return ''.join(input_string)
def move_to_end(palindrome_string,index):
palindrome_string = palindrome_string[:index] + palindrome_string[index+1:] + palindrome_string[index]
return palindrome_string
def make_palindrome(input_string):
"""sorts the string using bubble sort"""
sorted_string = bubbleSort(input_string)
length = len(input_string)
index = -3
palindrome_string = sorted_string
"""moves every second character from end in string to end"""
while index > -1*length:
palindrome_string = move_to_end(palindrome_string,index)
index-=2
print palindrome_string
make_palindrome("acbebaec")
Does it solve the problem?
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.