首先,您可以检查字符串是否可以转换为回文字符串。
只需使用字母数组(如果所有字母都是拉丁小写字母,则为26个字符),并计算输入字符串中每个字母的数量。
如果字符串长度为偶数,则所有字母计数应为偶数。
如果字符串长度为奇数,则所有字母计数应该全部是偶数,除了一个。
这个第一遍 O(n) 的处理就已经解决了所有 -1 的情况。
如果字符串长度为奇数,请从将具有奇数计数的元素移动到中间开始。
然后,您可以应用以下过程:
使用以下逻辑为长度为 N 的输入字符串 S 建立加权图:
对于索引从 0 到 N/2-1 的每个元素:
- 如果对称元素 S[N-index-1] 相同,则继续
- 如果不同,则在两个字符之间创建边(按字母顺序),或增加现有字符的权重
这个想法是当权重为偶数时,您可以通过一次交换形成两个对。
当权重为奇数时,您不能在一次交换中放置两个对,您的交换需要形成一个循环。
1. For instance "a b a b"
One edge between a,b of weight 2:
a - b (2)
Return 1
2. For instance: "a b c b a c"
a - c (1)
b - a (1)
c - b (1)
See the cycle: a - b, b - c, c - a
After a swap of a,c you get:
a - a (1)
b - c (1)
c - b (1)
Which is after ignoring first one and merge 2 & 3:
c - b (2)
Which is even, you get to the result in one swap
Return 2
3. For instance: "a b c a b c"
a - c (2)
One swap and you are good
在生成图表后,基本上要将每个边的权重/2(整数除法,例如7/3=3)添加到结果中
此外,要查找循环,并将每个循环的长度-1添加到结果中