问题描述

给定一个许可密钥字符串 s，仅由字母、数字字符和破折号组成。字符串由 n 个破折号分成 n+1 组。给定一个整数 k，重新格式化字符串，使每一组恰好包含 k 个字符，第一组可以少于 k 个字符但至少包含一个字符。用破折号分隔组，所有小写字母转换为大写。

解题思路

本题的要点在于理解分组规则：除了第一组外，其余每组恰好 k 个字符。这意味着我们需要先计算出总的有效字符数，然后确定第一组的大小。

算法步骤

  1. 去除破折号：

    • 使用 s.split("-") 将原字符串按破折号分割
    • 将所有非破折号部分拼接起来，得到所有有效字符的连续字符串

  2. 计算第一组长度：

    • 设总有效字符数为 sumLength
    • 第一组的长度 firstLen = sumLength % k
    • 如果 firstLen == 0（恰好整除），则第一组也应取 k 个字符

  3. 按组格式化：

    • 取前 firstLen 个字符作为第一组，转为大写
    • 从 firstLen 位置开始，每次取 k 个字符作为一组，组间用 "-" 分隔，每组转为大写

举例说明

示例 1：s = "5F3Z-2e-9-w", k = 4

  • 去除破折号后："5F3Z2e9w"，共 8 个字符
  • firstLen = 8 % 4 = 0，所以 firstLen = 4（整除时每组都取 4 个）
  • 第一组："5F3Z" → "5F3Z"
  • 第二组："2e9w" → "2E9W"
  • 结果："5F3Z-2E9W"

示例 2：s = "2-5g-3-J", k = 2

  • 去除破折号后："25g3J"，共 5 个字符
  • firstLen = 5 % 2 = 1
  • 第一组："2" → "2"
  • 第二组："5g" → "5G"
  • 第三组："3J" → "3J"
  • 结果："2-5G-3J"

关键点

  • 第一组可以比其他组短，但不能为空
  • 破折号在格式化后的字符串中仅作为分隔符出现，不能出现在开头或结尾
  • 所有字母必须转换为大写

复杂度分析

  • 时间复杂度：O(n)，需要遍历字符串一次，其中 n 为字符串长度。
  • 空间复杂度：O(n)，需要额外空间存储处理后的字符串。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
package code.J482;

public class J482 {
    public String licenseKeyFormatting(String s, int k) {
        StringBuilder sb = new StringBuilder();
        String[] strings = s.split("-");
        if (strings.length < 1) return "";
        int sumLength = 0;
        for (String string : strings) {
            sb.append(string);
            sumLength += string.length();
        }
        int firstLen = sumLength % k;
        if (firstLen == 0) firstLen = k;
        StringBuilder result = new StringBuilder();
        String str = sb.toString();
        result.append(str.substring(0, firstLen).toUpperCase());
        for (int i = firstLen; i < str.length(); i += k) {
            if (!result.isEmpty()) result.append("-");
            int end = Math.min(i + k, s.length());
            result.append(str.substring(i, end).toUpperCase());
        }
        return result.toString();
    }
}