【算法】【Python】能否构成回文字符串

原始题解

def testFunc(S):
    support = ["l","q","b"]
    lenS = len(S)
    for i in range(lenS):
        if i == 0 and S[-i-1] in support:
            S = S[-i-1] + S
        elif S[-i-1] in support:
            S = S[0:i] + S[-i-1] + S[i:]
        if S == S[::-1]:
            return True
    return False

T = int(input().strip())
for _ in range(T):
    S = input().strip()
    if S == S[::-1]:
        print("Yes")
    else:
        if testFunc(S):
            print("Yes")
        else:
            print("No")

最开始的思路，通过将字符串后面的字符向左边填充，然后检查是否是回文串（S == S[::-1]）以达到目的。原理上是可行的，但是这道题目给的输入字符串长度最大能到10^8，提交后只能通过70%测试点。

存在的问题：

回文检测的多次操作：每次检查一个字符串是否回文时，你都在重新生成字符串和进行多次判断，特别是当字符串长度非常大时，这种操作的时间复杂度非常高，容易导致超时。

频繁的字符串拼接：在每次发现字符可以插入时，你会构造一个新的字符串，这在Python中是一个低效的操作。因为字符串是不可变的，每次拼接都会创建新的字符串对象，导致时间复杂度高。

改进后题解

def testFunc(S):
    support = ["l", "q", "b"]
    n = len(S)
    left, right = 0, n - 1

    while left < right:
        if S[left] == S[right]:
            left += 1
            right -= 1
        elif S[right] in support:
            right -= 1
        else:
            return False
    return True

T = int(input().strip())
for _ in range(T):
    S = input().strip()
    if S == S[::-1]:
        print("Yes")
    else:
        if testFunc(S):
            print("Yes")
        else:
            print("No")

通过使用”双指针“（当然Python里没有指针，这里加了引号），设置了left和right”指针“，分别从字符串两边开始向内检查。

如果相等，则当前位置符合回文要求，继续向内检查，两个”指针都向内移动“。

如果不相等，但right所在位置的字符是可以插入的，那么在左边插入相同的字符成为了可能，就跳过这个字符。

如果right所在位置的字符不是可被插入的，并且不相等，那么说明这个字符串不能通过插入字符变为回文，直接返回False。