LeetCode 3216. 交换后字典序最小的字符串[简单]

. - 力扣（LeetCode）

题目

给你一个仅由数字组成的字符串 s，在最多交换一次相邻且具有相同 奇偶性 的数字后，返回可以得到的字典序最小的字符串。

相同奇偶性：如果两个数字都是奇数或都是偶数，则它们具有相同的奇偶性。例如，5 和 9、2 和 4 奇偶性相同，而 6 和 9 奇偶性不同。

示例 1：
- 输入： s = "45320"
- 输出： "43520"
- 解释：s[1] == '5' 和 s[2] == '3' 都具有相同的奇偶性，交换它们可以得到字典序最小的字符串。
示例 2：
- 输入： s = "001"
- 输出： "001"
- 解释：无需进行交换，因为 s 已经是字典序最小的。

提示：

2 <= s.length <= 100
s 仅由数字组成。

解题方法

字符串方法

相同奇偶性的数学性质：
两个奇数相加，和是偶数
两个偶数相加，和是偶数

因此相同奇偶性的两个数相加，和一定是偶数；

如果一个奇数和一个偶数相加，则和是奇数。

class Solution:def getSmallestString(self, s: str) -> str:small_str = s # 记录最小字符串for index, c in enumerate(s):if index == len(s) - 1:breaknext_c = s[index + 1]if c == next_c or (int(c) + int(next_c)) % 2 != 0:continue# 交换后的新字符串temp_str = s[0: index] + next_c + cif index < len(s) - 2:temp_str += s[index + 2:]# 更新最小字符串if temp_str < small_str:small_str = temp_strreturn small_str

分析复杂度

记字符串长度为n

时间复杂度：鉴于 Python字符串是不可变的，因此生成交换后的新字符串实际是一个字符串copy的过程，时间复杂度是O(n)，又因为字符串长度为n，即遍历了n次，所以时间复杂度是 $O(n^2)$
空间复杂度：small_str长度为n，遍历过程中始终存在一个长度为n的temp_str，因此空间复杂度为2n, 即 $O(n)$

贪心算法

优化点1：字符串是不可变的，因此交换字符位置需要复制整个字符串，时间复杂度为O(n).如果将字符串转为list，则交换字符位置仅需要O(1)的时间复杂度。
优化点2：贪心算法如果相同奇偶性的两个数字，
第一个数字小于第二个数字，则不需要交换（因为交换后字符串更大）；
反之，则需要交换，找到第一个可以交换的位置即可。

class Solution:def getSmallestString(self, s: str) -> str:t = list(s)for i in range(1, len(t)):x, y = t[i - 1], t[i]if (int(x) + int(y)) % 2 == 0 and x > y:t[i - 1], t[i] = y, xbreakreturn ''.join(t)