查找删除元素字符串时变为回文的索引

Question

我正在写这个黑客银行问题的解决方案-https://www.hackerrank.com/challenges/palindrome-index

我试过这个代码：

T = int(raw_input())

for t in xrange(T):
    s = raw_input()
    index = -1
    if s != s[::-1]:
        for i in xrange(len(s)):
            temp = s[:i:] + s[i+1::]
            if temp == temp[::-1]:
                index = i
                break
    print index

但是当我提交的时候，在14个测试用例中，大约有8个测试用例需要很长的时间来计算（大约5-7秒），其中1个需要10秒以上，所以HackerRank甚至没有显示结果（是否给出了正确的输出）。 我的代码似乎效率低下。请帮我把它开快点。在

Answer 1

最有效的方法是从左右两边检查，打破不平等：

for i in range(int(input())):
    s=input()
    if s==s[::-1]:
        print(-1)
    else:
        for i in range(int(len(s)/2)):
            if s[i]!=s[len(s)-1-i]:
                print(i if ((s[:i]+s[i+1:])==(s[:i]+s[i+1:])[::-1]) else len(s)-1-i)
                break

显然我也是那个网站的一员，执行我的代码，它以0.01秒和0.02秒通过了所有测试用例

Answer 2

加快代码速度的最简单方法是删除每个索引的切片，以防字符串不是回文。如果最大长度的字符串不是回文，下面的一行将生成超过200000个片段：temp = s[:i:] + s[i+1::]。在

您可以从开始和开始检查字符串，直到发现差异为止。一旦找到，你就可以生成第一个或最后一个字母被删除的切片，并检查它是否是回文。如果您删除了第一个字符而结果不是回文，那么您知道最后一个字符是正确的解决方案，因为问题陈述保证：

T = int(raw_input())

for t in xrange(T):
    s = raw_input()
    length = len(s)
    for i in xrange(length / 2):
        if s[i] != s[length - i - 1]:
            if s[i + 1:length - i] == s[length - i - 1:i:-1]:
                print i
            else:
                print length - i - 1
            break
    else:
        print -1