What is the best approach for solving the License Key Formatting problem?

The best approach is to iterate over the string, build groups, handle the first group separately, and manage the conversion to uppercase and insertion of dashes.

How can I avoid extra dashes when formatting the license key?

Ensure that you only insert dashes between groups and not at the start or end of the string.

What is the time complexity of the License Key Formatting problem?

The time complexity is O(N), where N is the length of the input string `s`.

Can I use built-in functions for string manipulation in this problem?

Yes, built-in string manipulation functions like `upper()` and `join()` can help simplify the implementation.

What should I focus on when solving problems like License Key Formatting?

Focus on managing string groups, handling edge cases with the first group, and ensuring accurate formatting throughout.

#482

Easy

auto_awesomeString-driven solution strategy

LeetCode 题解工作台

密钥格式化

给定一个许可密钥字符串 s ，仅由字母、数字字符和破折号组成。字符串由 n 个破折号分成 n + 1 组。你也会得到一个整数 k 。我们想要重新格式化字符串 s ，使每一组包含 k 个字符，除了第一组，它可以比 k 短，但仍然必须包含至少一个字符。此外，两组之间必须插入破折号，并且应该将所有小写字…

字符串

题目描述

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

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

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

示例 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.length <= 10⁵
s 只包含字母、数字和破折号 '-'.
1 <= k <= 10⁴

lightbulb

解题思路

方法一：模拟

我们先统计出字符串 $s$ 中除去破折号之外的字符个数，并对 $k$ 取模，得到第一组字符的个数。如果为 $0$ ，则第一组字符个数为 $k$ ，否则为取模的结果。

接着我们遍历字符串 $s$ ，对于每个字符，如果是破折号，则跳过；否则将其转换为大写字母，并将其加入答案字符串中。同时，我们维护一个计数器 $cnt$ ，表示当前组还剩余的字符个数，当 $cnt$ 减为 $0$ 时，我们需要更新 $cnt$ 为 $k$ ，并且如果当前字符不是最后一个字符，我们需要在答案字符串中加入一个破折号。

最后，我们移除答案字符串末尾的破折号，并返回答案字符串。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串 $s$ 的长度。忽略答案字符串的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def licenseKeyFormatting(self, s: str, k: int) -> str:
        n = len(s)
        cnt = (n - s.count("-")) % k or k
        ans = []
        for i, c in enumerate(s):
            if c == "-":
                continue
            ans.append(c.upper())
            cnt -= 1
            if cnt == 0:
                cnt = k
                if i != n - 1:
                    ans.append("-")
        return "".join(ans).rstrip("-")

speed

复杂度分析

指标	值
时间	O(N)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
The candidate correctly identifies a string-driven solution pattern.
question_mark
The candidate demonstrates an understanding of how to handle edge cases like the first group.
question_mark
The candidate implements the uppercase conversion and dash management effectively.

warning

常见陷阱

外企场景

error
Failing to handle the first group properly, leading to incorrect group sizes.
error
Incorrectly placing dashes or leaving extra ones at the end of the string.
error
Not converting lowercase letters to uppercase as specified in the problem.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Reformatting strings with different delimiters (e.g., spaces, commas).
arrow_right_alt
Handling a string with no dashes, where groups must still be formed.
arrow_right_alt
Adjusting the number of groups or the size of each group dynamically.

help

常见问题

外企场景

继续练习

#481 神奇字符串 #488 祖玛游戏 #474 一和零