蓝桥杯训练—完美的代价
文章目录
- 一、题目
- 二、示例
- 三、解析
- 四、代码
一、题目
回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。
交换的定义是：交换两个相邻的字符
例如mamad
第一次交换ad：mamda
第二次交换md：madma
第三次交换ma：madam
输入格式：
输入一行，是一个字符串，长度为n，只包括小写字母
输出格式：
如果可能，输出最少的交换次数
否则输出impossible
二、示例
输入：
mamad
输出：
3
三、解析
无需考虑字符串的长度，当每个字母的出现次数都为偶数时，该字符串必定能构成回文串；当字符串中出现奇数个出现次数为奇数的字母时，也能构成回文串；但是当出现偶数个出现次数为奇数的字母时则不能构成回文串。
基于此，可以统计字母出现的次数，以及出现次数为奇数的字母的个数。
四、代码
python代码：
pal = list(input())
n = len(pal)
count = flag = 0
m = n - 1
for i in range(m):
for k in range(m, i - 1, -1):
if k == i:
if n % 2 == 0 or flag == 1:
print("impossible")
exit()
flag = 1
count += int(n / 2) - i
elif pal[k] == pal[i]:
for j in range(k, m):
pal[j], pal[j + 1] = pal[j + 1], pal[j]
count += 1
m -= 1
break
print(count)
运行结果：
