LeetCode 482. 密钥格式化

2022-04-29 HGNULB 约 8 分钟

文章信息 7 个分类 1 个标签

分类

题目描述

✅ 482. 密钥格式化

题意分析

输入是一个由字母、数字和短横线组成的字符串 s，以及一个正整数 k。要求先把原有的短横线全部丢掉，只保留字母数字，再把这串字符重新用短横线切分成若干组：除第一组外，每组恰好 k 个字符；第一组长度在 $1$ 到 $k$ 之间，可以短，但不能为空。所有小写字母要转成大写。

题面里「除第一组外每组都是 k 个」这句话，是整道题唯一的难点信号：分组的锚点在末尾而不是开头。如果从左往右扫，第一组该留几个字符必须先知道有效字符总数，也就是要么先做一遍统计再做一遍切分，要么先把有效字符抽出来再算。反过来从右往左扫，每凑满 k 个就切一刀，剩下多少算多少，第一组的「余数长度」自然就出来了，完全不需要预先知道总数。

边界上要留意三种输入：整串全是短横线（有效字符数为 $0$，答案是空串，绝不能输出一个孤零零的 -）；有效字符数恰好是 k 的整数倍（此时第一组正好是 k 个，中间不能多出前导横线）；有效字符数小于 k（整串就是一组，一根横线都不加）。字符串长度可达 $10^5$，要求线性时间，同时不要在循环里反复做字符串拼接。

解法：从后向前分组

核心思路

最直白的做法是两趟：第一趟把 s 里所有非 - 的字符抽出来大写化，得到长度为 m 的干净串；第二趟算出第一组长度 first = m % k（为 $0$ 时取 k），然后按 first, k, k, ... 切。这个做法没错，但它需要一个额外的中间串，而且 m % k == 0 这个特判很容易在白板上写漏。

瓶颈在于「第一组长度」这个量依赖全局统计。观察一下：所有的完整组都紧贴着字符串末尾，第一组是被挤出来的残余。也就是说，如果从末尾往前数，第 k、第 2k、第 3k 个有效字符之前都要插一根横线，这个规则对所有位置是统一的，不需要区分「第一组」和「其他组」。残余部分因为凑不满 k 个，自然不会触发插入，也就自然成为长度小于 k 的第一组。

于是维护的不变量是：逆序扫描过程中，count 表示「当前正在填充的这一组已经收进了几个有效字符」，取值恒在 $[0, k]$ 区间内。只有在准备写入一个新字符且 count == k 时才补一根横线并把 count 归零。这样构造出来的是答案的逆序串，最后整体反转即可。之所以要延迟到「准备写下一个字符时」才补横线，而不是「凑满 k 个立刻补」，正是为了避免末尾多出一根悬空的横线——如果有效字符恰好是 k 的倍数，立刻补的写法会在结果最前面留下一个前导 -。

解题步骤

准备一个 StringBuilder（Go 里是 []byte）作为缓冲区，并按 len(s) 预留容量。理由：结果长度不会超过原串长度（横线只会变少不会变多），一次分配到位可以避免扩容拷贝。

用下标 i 从 s.length() - 1 递减到 $0$ 逆序遍历。理由：分组锚点在末尾，逆序扫描才能让「每 k 个切一刀」这条规则对所有组统一生效。

遇到 - 直接 continue。理由：原串的分组方式与答案无关，题目只关心有效字符的相对顺序，横线是纯噪声。

在追加当前字符之前判断 count == k：成立就先追加一个 - 并把 count 置 $0$。理由：这是「延迟插入」，保证横线永远出现在两个有效字符之间，末尾不会悬空。

追加大写化后的字符，count++。Java 用 Character.toUpperCase；Go 里手动判断 ch >= 'a' && ch <= 'z' 再减 'a' - 'A'。理由：题目保证只有字母数字，数字和大写字母都不受影响，这个转换是幂等的。

循环结束后把缓冲区整体反转再转成字符串。理由：整个过程是倒着构造的，反转一次就还原成正序；这比每次往头部插入字符要快，头插是 $O(n)$ 的，总代价会退化成 $O(n^2)$。

以 s = "2-5g-3-J", k = 2 走一遍：count = 0，缓冲区空。i = 7 取到 J，count != k，写入 J，count = 1。i = 6 是 -，跳过。i = 5 取到 3，count = 1 != 2，写入 3，count = 2。i = 4 是 -，跳过。i = 3 取到 g，此时 count == 2 == k，先写入 - 并把 count 归零，再写入大写的 G，count = 1。i = 2 取到 5，count = 1 != 2，写入 5，count = 2。i = 1 是 -，跳过。i = 0 取到 2，count == 2 == k，先写 - 归零，再写 2，count = 1。此时缓冲区是 J3-G5-2，反转得到 2-5G-3J，与期望一致；注意最左边的 2 单独成组，长度 $1 < k$，正是那个被挤出来的残余组。

代码实现

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)$，其中 $n$ 是字符串 s 的长度。逆序扫描每个字符恰好访问一次，追加操作在均摊意义下是 $O(1)$，最后的整体反转再走一遍缓冲区，总共不超过三次线性遍历。

空间复杂度：$O(n)$，缓冲区最多存下所有有效字符加上插入的横线，长度不超过原串。除此之外只用了 count 一个计数器，是 $O(1)$ 的额外空间；如果不把返回值算作额外空间，那么本解法是原地常数空间的。

关键点总结

当分组规则里出现「除第一组外每组固定长度」这类描述时，反向遍历几乎总能把不规则的那一组消化掉——把不规则的部分留在扫描的最后，它就不再需要特判。这个技巧在数字千分位格式化、大整数按四位分节、时间戳倒着切分等场景里可以直接复用。

「延迟插入分隔符」是构造类字符串题的通用手法：不要在凑满一组时立刻加分隔符，而是在确认还有下一个元素要写时再加，这样天然避免了首尾悬空的分隔符，比事后 if (sb.length() > 0) sb.deleteCharAt(0) 这种补丁写法干净得多。

倒序构造 + 一次性反转，比正序构造时反复头插要好一个量级。面试里被追问「为什么不用 insert(0, ch)」时，要能立刻答出头插导致数组整体后移、总复杂度退化到 $O(n^2)$。

大小写转换要挑不会误伤的写法。Character.toUpperCase 对数字是恒等映射，所以可以无脑套；但如果手写位运算 ch & ~32，数字字符会被改坏，这是面试官很喜欢挖的坑。

面试视角：这题被华为、腾讯拿来考的核心不是算法，而是边界意识和代码整洁度。写完后主动报出「全横线输入」「长度恰为 k 倍数」两个用例并口头验证一遍，比写得快更能加分。

易错点总结

错误写法：在 count == k 时先追加横线再判断是否还有字符写成了「追加字符后立刻 if (count == k) sb.append('-')」→ 用例 s = "abcd", k = 2 → 缓冲区变成 dc-ba-，反转后得到 -AB-CD，多出一个前导横线，答案错误。

错误写法：正序遍历并直接每 k 个切一刀 → 用例 s = "2-5g-3-J", k = 2 → 得到 25-G3-J，最后一组只有 1 个字符，而题目要求短的那一组必须在开头，输出与期望的 2-5G-3J 不符。

错误写法：忘记跳过原串里的 -，把它当成有效字符计入 count → 用例 s = "---", k = 3 → 输出 --- 而不是空串，且计数完全错位。

错误写法：用 s.replace("-", "").toUpperCase() 预处理后按 first = m % k 切分，但漏掉 m % k == 0 时应取 first = k 的特判 → 用例 s = "abcd", k = 2 → first = 0，第一组为空，输出 -AB-CD，多出前导横线。

错误写法：用 String 拼接代替 StringBuilder，写成 res = ch + res 做头插 → 用例 s 长度为 $10^5$ → 每次拼接都要复制整个已有结果，总操作量约 $5 \times 10^9$，直接超时。

错误写法：大写化用位运算 ch & 0xDF（即清掉第 5 位）→ 用例 s = "5F3Z-2e-9-w", k = 4 → 数字 5 的 ASCII 是 0x35，清位后变成 0x15 这个控制字符，输出出现乱码。

错误写法：Go 里用 for i := range s 反向遍历 rune 或者用 strings.Builder 却没做反转，直接返回正序缓冲 → 用例 s = "2-5g-3-J", k = 2 → 输出 J3-G5-2，整个字符串是反的。

错误写法：把 count 的判断写成 count % k == 0 且不区分 count == 0 的初始状态 → 用例 s = "abc", k = 3 → 第一个字符写入前 count 就是 $0$，0 % 3 == 0 成立，缓冲区末尾先塞进一根横线，反转后输出 ABC-，尾部多横线。

错误写法：认为 k 可能为 $0$ 而加了除零保护，或反过来在 k >= s.length() 时提前 return s → 用例 s = "a-b", k = 5 → 直接返回原串 a-b，既没删横线也没大写化，正确答案应是 AB。

相似题目

题目	难度	考察点
58. 最后一个单词的长度	简单	同样靠逆序扫描消化尾部空白，但只统计长度不构造结果
151. 反转字符串中的单词	中等	分隔符处理升级为「压缩连续空格」，且要求单词整体顺序反转
443. 压缩字符串	中等	分组依据从固定长度变成相同字符游程，且必须原地写回数组
38. 外观数列	中等	分组后还要把「个数 + 字符」编码进下一轮，是迭代式构造
68. 文本左右对齐	困难	每行容量固定但填充空格需按余数均摊，末行规则与其余行不同