2
\$\begingroup\$

This code finds the index in the string and removes the one which will make the string a palindrome. If the string is already a palindrome, it should return -1.

This code works correct, but I am looking for a better implementation of it. Here is the problem description.

def palindrome(string):
    return string == string[::-1]

def palindrome_index(string, start, end):
    while start < end:
        if string[start] == string[end]:
            start, end = start+1, end-1
            continue
        if palindrome(string[start:end]): return end
        return start
    return -1
N = input()
strings = [str(raw_input()) for _ in range(N)]
for string in strings:
    print palindrome_index(string, 0, len(string)-1)

Can this be written shorter? The size of input strings can be as large as 105, hence a recursive approach won't work.

\$\endgroup\$
1
\$\begingroup\$

Flow

The continue and returns inside the while loop make me feel the loop is doing too much. I would say that the loop should be for moving start and end and then put the logic outside of it:

while ( start < end and string[start] == string[end] ):
    start, end = start + 1, end - 1

# now figure out the result

Result

The problem states that all strings that are not already palindromes are only off by one character.

Our loop moved start and end such that if start == end, then the string is a palindrome. It has also moved these indices such that if the string is not a palindrome, one of them is 'pointing' to the character that needs to be removed.

To figure out which index is correct, I chose to compare the character pointed to by start to the character pointed to by end - 1.

if ( start == end ):
    return -1
elif ( string[ start ] == string[ end - 1 ] ):
    return end
else:
    return start

Palindrome Function

You don't need this function at all because we know that if the string is not a palindrome, it is only off by one character. We were able to figure out the index of this character just by moving start and end

Anyway, since the function returns a boolean, it should be named isPalindrome

\$\endgroup\$
  • 1
    \$\begingroup\$ string[ start ] == string[ end - 1 ] does not cover all the test cases, you need to out another check like string[start+1] == string[end-2] Take 'abaab' for example. \$\endgroup\$ – Anubhav Agarwal Sep 20 '14 at 8:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.