LeetCode 482. 密钥格式化
题目描述
题意分析
忽略原有短横线，保留字母和数字的相对顺序，并把小写字母转为大写。重新分组后，除最左组外，每组都恰好有
k个有效字符；最左组可以更短，但不能人为生成空组。
解法：从后向前分组
核心思路
[!blue]
允许不足
k个字符的组位于最左边，因此从右向左扫描更直接：先把右侧各组填满，扫描结束时最后留下的一组自然就是最左组，无需预先统计有效字符总数。
count表示当前正在构造的组已有多少个有效字符。原短横线直接跳过，不增加计数；准备写入下一个字母或数字时，如果count == k，先写一个分隔符并将计数清零，再写入大写字符。已经封闭的组始终恰好有k个字符，未封闭的组长度则不超过k。分隔符要等到确认还有有效字符时才追加。这样每个分隔符两边都有字符，恰好整除
k时也不会多出一个空组；若只剩原短横线，同样不会再追加分隔符。缓冲区按原字符的逆序构造，最后整体反转，字符相对顺序就恢复了，组间分隔也落在正确位置。若最后一组不足
k个，反转后它恰好位于最左侧。
解题步骤
- 跳过原横线。
- 当前组已满时，先追加分隔符并清空组计数。
- 追加大写字符，计数加一。
- 整体反转缓冲区后返回。
没有有效字符时返回空字符串；有效字符不足
k个时只产生一组；k=1时每个有效字符单独成组。这些情况都由同一套计数规则处理。
代码实现
class Solution {
public String licenseKeyFormatting(String s, int k) {
StringBuilder sb = new StringBuilder();
int count = 0;
for (int i = s.length() - 1; i >= 0; i--) {
char ch = s.charAt(i);
if (ch == '-') {
continue;
}
// 确认还有当前有效字符要写时，才补组间分隔符
if (count == k) {
sb.append('-');
count = 0;
}
sb.append(Character.toUpperCase(ch));
count++;
}
// 构造顺序是逆向的，最后统一反转
return sb.reverse().toString();
}
}
func licenseKeyFormatting(s string, k int) string {
buf := make([]byte, 0, len(s))
count := 0
for i := len(s) - 1; i >= 0; i-- {
ch := s[i]
if ch == '-' {
continue
}
// 确认还有当前有效字符要写时，才补组间分隔符
if count == k {
buf = append(buf, '-')
count = 0
}
if ch >= 'a' && ch <= 'z' {
ch = ch - 'a' + 'A'
}
buf = append(buf, ch)
count++
}
// 构造顺序是逆向的，最后统一反转
for i, j := 0, len(buf)-1; i < j; i, j = i+1, j-1 {
buf[i], buf[j] = buf[j], buf[i]
}
return string(buf)
}
复杂度分析
- 时间复杂度：$O(n)$，扫描、缓冲追加与反转总量线性。
- 空间复杂度：$O(n)$，用于构造缓冲。有效字符数不超过
n，每个有效字符前最多新增一个分隔符，所以结果长度仍是线性的。
关键点总结
[!green]
- 从右侧填满每组，让唯一可能的短组自然留在左侧。
- 只有字母数字参与计数，旧分隔符的位置没有保留价值。
- 延迟插入分隔符，避免单独处理首尾空组。
易错点总结
[!yellow]
- 一组刚满就立即加横线，可能留下前导横线。
- 顺向每 k 个直接分组，会把短组放到末尾。
- 不做反转就返回，字符顺序会颠倒。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1556. 千位分隔数 | 简单 | 同样从右向左分组插入分隔符；该题组长固定为三，本题需要先过滤并规范字符。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！