同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给你一个只包含小写英文字母的字符串 s
。
每一次 操作 ,你可以选择 s
中两个 相邻 的字符,并将它们交换。
请你返回将 s
变成回文串的 最少操作次数 。
注意 ,输入数据会确保 s
一定能变成一个回文串。
示例 1:
输入:s = "aabb" 输出:2 解释: 我们可以将 s 变成 2 个回文串,"abba" 和 "baab" 。 - 我们可以通过 2 次操作得到 "abba" :"aabb" -> "abab" -> "abba" 。 - 我们可以通过 2 次操作得到 "baab" :"aabb" -> "abab" -> "baab" 。 因此,得到回文串的最少总操作次数为 2 。
示例 2:
输入:s = "letelt" 输出:2 解释: 通过 2 次操作从 s 能得到回文串 "lettel" 。 其中一种方法是:"letelt" -> "letetl" -> "lettel" 。 其他回文串比方说 "tleelt" 也可以通过 2 次操作得到。 可以证明少于 2 次操作,无法得到回文串。
提示:
1 <= s.length <= 2000
s
只包含小写英文字母。s
可以通过有限次操作得到一个回文串。由于题目保证原串一定可以变成回文串,那么原串中最多只有一种字母出现奇数次。如果有一种字母出现奇数次,那么将该字母中排在最中间的字符移动到字符串中间,剩下的字符可以转化为所有字母均出现偶数次的情况。
贪心算法是:每次固定字符串最左边的字母 $a$ 不变,找出距离字符串右侧最近的 $a$,把它交换到字符串最右边。这样字符串的头尾字母就相等了。把字符串的头尾去掉,就变成了子问题。把所有子问题的答案加起来就是最少交换次数。
由于数据范围较小,通过 ${O}(n^2)$ 的模拟即可通过本题。
证明:
构造回文串的过程,实际上是每次选择一对字母并把它们交换到字符串头尾的过程。考虑字母 $x$ 和字母 $y$ 哪个先选,分以下情况讨论:
上述讨论可以得到结论:每次交换最外边出现的字母不劣。因此贪心解法成立。
class Solution:
def minMovesToMakePalindrome(self, s: str) -> int:
cs = list(s)
ans, n = 0, len(s)
i, j = 0, n - 1
while i < j:
even = False
for k in range(j, i, -1):
if cs[i] == cs[k]:
even = True
while k < j:
cs[k], cs[k + 1] = cs[k + 1], cs[k]
k += 1
ans += 1
j -= 1
break
if not even:
ans += n // 2 - i
i += 1
return ans
class Solution {
public int minMovesToMakePalindrome(String s) {
int n = s.length();
int ans = 0;
char[] cs = s.toCharArray();
for (int i = 0, j = n - 1; i < j; ++i) {
boolean even = false;
for (int k = j; k != i; --k) {
if (cs[i] == cs[k]) {
even = true;
for (; k < j; ++k) {
char t = cs[k];
cs[k] = cs[k + 1];
cs[k + 1] = t;
++ans;
}
--j;
break;
}
}
if (!even) {
ans += n / 2 - i;
}
}
return ans;
}
}
class Solution {
public:
int minMovesToMakePalindrome(string s) {
int n = s.size();
int ans = 0;
for (int i = 0, j = n - 1; i < j; ++i) {
bool even = false;
for (int k = j; k != i; --k) {
if (s[i] == s[k]) {
even = true;
for (; k < j; ++k) {
swap(s[k], s[k + 1]);
++ans;
}
--j;
break;
}
}
if (!even) ans += n / 2 - i;
}
return ans;
}
};
func minMovesToMakePalindrome(s string) int {
cs := []byte(s)
ans, n := 0, len(s)
for i, j := 0, n-1; i < j; i++ {
even := false
for k := j; k != i; k-- {
if cs[i] == cs[k] {
even = true
for ; k < j; k++ {
cs[k], cs[k+1] = cs[k+1], cs[k]
ans++
}
j--
break
}
}
if !even {
ans += n/2 - i
}
}
return ans
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。