0482. 密钥格式化

ITCharge大约 3 分钟

---

0482. 密钥格式化

标签：字符串
难度：简单

题目链接

0482. 密钥格式化 - 力扣

题目大意

描述：

给定一个许可密钥字符串 $s$ ，仅由字母、数字字符和破折号组成。字符串由 $n$ 个破折号分成 $n + 1$ 组。你也会得到一个整数 $k$ 。

我们想要重新格式化字符串 $s$ ，使每一组包含 $k$ 个字符，除了第一组，它可以比 $k$ 短，但仍然必须包含至少一个字符。此外，两组之间必须插入破折号，并且应该将所有小写字母转换为大写字母。

要求：

返回「重新格式化的许可密钥」。

说明：

$1 \le s.length \le 10^{5}$ 。
$s$ 只包含字母、数字和破折号 '-'。
$1 \le k \le 10^{4}$ 。

示例：

示例 1：

输入：S = "5F3Z-2e-9-w", k = 4
输出："5F3Z-2E9W"
解释：字符串 S 被分成了两个部分，每部分 4 个字符；
     注意，两个额外的破折号需要删掉。

示例 2：

输入：S = "2-5g-3-J", k = 2
输出："2-5G-3J"
解释：字符串 S 被分成了 3 个部分，按照前面的规则描述，第一部分的字符可以少于给定的数量，其余部分皆为 2 个字符。

解题思路

思路 1：模拟

这道题的思路比较直观，我们需要重新格式化密钥字符串。

具体思路如下：

预处理：遍历字符串 $s$ ，去除所有破折号，并将小写字母转换为大写字母，得到一个新的字符串 $res$ 。
分组插入破折号：从后往前遍历处理后的字符串 $res$ ，每 $k$ 个字符插入一个破折号。
返回结果：返回格式化后的字符串。

注意：最后一组（即字符串开头的部分）的长度可能小于 $k$ ，这是允许的，因为题目要求第一组可以比 $k$ 短。

算法步骤：

遍历原始字符串 $s$ ，将所有有效的字符（字母和数字）收集起来，并转为大写，存储在列表 $chars$ 中。
使用变量 $group\_size$ 记录当前组的字符数，初始化为 $0$ 。
从后往前构建结果字符串：将 $chars$ 中的字符从后往前依次添加到结果中，每 $k$ 个字符添加一个破折号。

思路 1：代码

class Solution:
    def licenseKeyFormatting(self, s: str, k: int) -> str:
        # 收集所有有效字符并转为大写
        chars = []
        for char in s:
            if char != '-':
                chars.append(char.upper())
        
        # 如果所有字符都是破折号，返回空字符串
        if not chars:
            return ""
        
        # 从后往前构建结果
        res = []
        group_size = 0  # 当前组的字符数
        
        for i in range(len(chars) - 1, -1, -1):
            # 添加字符
            res.append(chars[i])
            group_size += 1
            
            # 每 k 个字符添加一个破折号（最后不添加）
            if group_size == k and i > 0:
                res.append('-')
                group_size = 0
        
        # 反转结果字符串
        return ''.join(res[::-1])

思路 1：复杂度分析

时间复杂度： $O(n)$ ，其中 $n$ 是字符串 $s$ 的长度。需要遍历字符串两次（收集字符和构建结果）。
空间复杂度： $O(n)$ ，需要额外的空间存储处理后的字符和结果字符串。