https://leetcode.com/problems/minimum-number-of-moves-to-make-palindrome/
贪心，比较难想到

个人解答

  1. class Solution:
  2.     def minMovesToMakePalindrome(self, s: str) -> int:
  3.         s = list(s)
  4.         res = 0
  5.         while s:
  6.             i = s.index(s[-1])
  7.             if i == len(s) - 1:
  8.                 res += len(s) // 2
  9.                 del s[-1]
  10.             else:
  11.                 res += i
  12.                 del s[i]
  13.                 del s[-1]
  15.         return res

题目分析

就贪心就好，哎，想的太多了，没做出来。

看解答，其实就是对于每一个端点的值，找出另一端最靠近那端的index。

为什么这么可以呢？需要验证两个部分：

  1. 最短的更改，最终的端点一定是两端的其中一个
  2. 最短的更改，两遍选任意一个端点都可以

第一点，以a ... b为例，如果a/ b作为端点，则匹配之后，可以剔除掉，不影响之后的交换。如果a/b匹配到中间，那么在之后的交换过程中，会经过匹配好的a/b，会多出两个swap。
最优情况下，不把a/b作为端点的swap数量和作为端点的swap数量相同，比如：acbacb

第二点，考虑一个通用的例子：a ... b ... a ... b，第二个a是最右边的a，第一个b是最左边的b。那么想要匹配两者，必然会经历ab ... ba这个过程：
ab ... a ... b-> ba ... a ... b -> ba ... ab<- **ab ... ba**
a ... b ... ab-> a ... b ... ba -> ab ... ba<- **ab ... ba**
两者最后都需要同样的步数，因此选择哪个无所谓。

所以简单贪心就好了。
另外针对不能匹配的点，说明是最中心的，需要移动到中心。