※ [本文转录自 Python 看板 #1Sl-UKEn ]
作者: suhang (suhang) 看板: Python
标题: [问题] 最小交换次数使字符两两一致
时间: Wed Apr 24 12:35:29 2019
问最小交换次数，使字符两两一致
例如 abcabc -> aabbcc or bbaacc or ccaabb 皆可
https://paste.ubuntu.com/p/4g2wbn5S2P/
这题感觉好像DP, 但不知道怎么DP
我写了一个recursie, 可以找到aabbcc但是又无法证明这是"最小"次数
从 i = 0开始，
如果 s[i] != s[i+1] 那就开始线性搜寻可以交换的字符，交换之后递归往下
我这个做法是greedy吗？
遇到不相同字符，去找最近可以交换过来的字符，(感觉很贪婪)
(我一直很不了解greedy的精神)
请问这题该怎么解呢? tks