跳至主要內容

482. 密钥格式化

482. 密钥格式化

🟢   🔖  字符串  🔗 力扣open in new window LeetCodeopen in new window

题目

You are given a license key represented as a string s that consists of only alphanumeric characters and dashes. The string is separated into n + 1 groups by n dashes. You are also given an integer k.

We want to reformat the string s such that each group contains exactly k characters, except for the first group, which could be shorter than k but still must contain at least one character. Furthermore, there must be a dash inserted between two groups, and you should convert all lowercase letters to uppercase.

Return the reformatted license key.

Example 1:

Input: s = "5F3Z-2e-9-w", k = 4

Output: "5F3Z-2E9W"

Explanation: The string s has been split into two parts, each part has 4 characters.

Note that the two extra dashes are not needed and can be removed.

Example 2:

Input: s = "2-5g-3-J", k = 2

Output: "2-5G-3J"

Explanation: The string s has been split into three parts, each part has 2 characters except the first part as it could be shorter as mentioned above.

Constraints:

  • 1 <= s.length <= 10^5
  • s consists of English letters, digits, and dashes '-'.
  • 1 <= k <= 10^4

题目大意

给定一个许可密钥字符串 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^5
  • s 只包含字母、数字和破折号 '-'.
  • 1 <= k <= 10^4

解题思路

  1. 去除破折号和转换为大写：

    • 使用正则表达式 /-/g 删除所有破折号。
    • 将剩余字符转换为大写。

  2. 分组逻辑：

    • 计算第一组的长度：firstLength。
    • 如果第一组的长度不为 0，将其单独截取出来。
    • 从第一组后面的字符开始，每 k 个字符截取并添加到结果数组中。

  3. 拼接结果：

    • 使用 join('-') 将所有分组用破折号连接成最终结果字符串，并返回。

复杂度分析

  • 时间复杂度：O(n)，其中 n 是字符串的长度。
    • 去除破折号和转换为大写，遍历字符串一次，时间复杂度为 O(n)。
    • 分组操作，遍历整个字符串，分成若干组，每组 k 个字符，时间复杂度为 O(n)。
    • 拼接字符串，使用 join 拼接分组数组，时间复杂度为 O(n)。
    • 总时间复杂度为 O(n)。
  • 空间复杂度：O(n)，用于存储去除破折号后的字符串和结果数组。

代码

/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var licenseKeyFormatting = function (s, k) {
	// 删除破折号并将字符转换为大写
	let cleanStr = s.replace(/-/g, '').toUpperCase();

	// 从后向前分组
	let result = [];
	let firstLength = cleanStr.length % k; // 第一组可能长度小于 k

	// 第一组（如果长度不为 0）
	if (firstLength > 0) {
		result.push(cleanStr.slice(0, firstLength));
	}

	// 其余组，每 k 个字符
	for (let i = firstLength; i < cleanStr.length; i += k) {
		result.push(cleanStr.slice(i, i + k));
	}

	// 用破折号连接所有分组并返回结果
	return result.join('-');
};
Copyright © 2024 2xiao