跳转至

3216. 交换后字典序最小的字符串

#python #leetcode #pairwise

题目描述

关联：https://leetcode.cn/problems/lexicographically-smallest-string-after-a-swap/description/

题目描述

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

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

本题的范围是 \(2 \leq \text{len}(s) \leq 100\)。

解题思路

pairwise() 秒了

Python 中的 itertools.pairwise() 函数可以用来生成一个可迭代对象，该对象包含了输入迭代器中的相邻元素对。

即 pairwise(ABCDEF) => AB BC CD DE EF

它相当于：

def pairwise(iterable):
    # pairwise('ABCDEFG') → AB BC CD DE EF FG

    iterator = iter(iterable)
    a = next(iterator, None)

    for b in iterator:
        yield a, b
        a = b

但是 Python 中无法实现字符串的字符交换，因为 Python 中的字符串是不可变对象。

有两个方法可以取代这个问题：

  • 使用 slice，比如确定了 index 之后可以直接 return s[:index] + s[index + 1] + s[index] + s[index + 2:]
  • 把 str 转换成 list，然后 s[index], s[index + 1] = s[index + 1], s[index]

两种方法的时间复杂度都是 \(O(n)\)。

完整题解

使用 slice

from itertools import pairwise

class Solution:
    def getSmallestString(self, s: str) -> str:
        for index, (a, b) in enumerate(pairwise(s)):
            a, b = int(a), int(b)
            if a % 2 == b % 2 and a > b:
                return s[:index] + s[index + 1] + s[index] + s[index + 2:]

        return s

使用 list

from itertools import pairwise

class Solution:
    def getSmallestString(self, s: str) -> str:
        s = list(s)
        for index, (a, b) in enumerate(pairwise(s)):
            a, b = int(a), int(b)
            if a % 2 == b % 2 and a > b:
                s[index], s[index + 1] = s[index + 1], s[index]
                return ''.join(s)

        return ''.join(s)

复杂度分析

时间复杂度：\(O(n)\)，其中 \(n\) 是字符串 s 的长度。我们只需要遍历一次字符串 s。

空间复杂度：\(O(1)\)。

评论