回文串问题
问题描述
输入一个字符串，若他是回文串，直接输出。
若不是回文串，让他补充成一个最短的回文串后输出。
样例1
11211
输出1
11211
样例2
abcb
输出2
abcba
思路
以样例2为例：
abcb，从后往前扫描，找到bcb是当前最长的回文串。
返回0，指的是索引0后面的位置都是回文串，补上前面的部分，即a(bcb)a。
输出abcba
再比如：
1233，从后往前扫描，找到33是当前最长的回文串。
返回1，[0,1]是需要逆序补充的字符串，即12(33)21
输出123321
解题步骤
若已经是回文串，则直接输出。若不是：
step1：从后往前找，找到从后往前的最长回文串的索引位置
step2：将前面的字符串逆序输出。
PS：如果题目改成了对称字符串，即输入abcb，输出abcbbcba，则在判断回文的时候加上len(s)%2==0 的判断条件即可。
代码
def isRe(s):
return len(s)%2==0 and s == s[::-1]
def getLargeRe(s):
'''从后往前找最长回文串， 返回一个索引值。如1233返回1,123返回1，指的是索引之后的串是回文串'''
s_len = len(s)
index = s_len - 1
max_index = s_len - 1
while index >= 0:
if isRe(s[index:]):
max_index = index-1
index -= 1
return max_index
if __name__ == '__main__':
while True: #这里用来测试
s = input()
if isRe(s): print(s)
else:
max_index = getLargeRe(s)
# print(max_index)
s = s + s[0:max_index+1][::-1]
print(s)
分析
这里用了python的字符串切片，实际上时间复杂度应该还是O(N²)，空间复杂度O(N)
京公网安备 11010502036488号