leetcode
leetcode 401 ~ 450
密钥格式化

密钥格式化

难度:

标签:

题目描述

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

代码结果

运行时间: 22 ms, 内存: 16.9 MB


/*
 * 思路:
 * 1. 使用Stream将字符串中的破折号去除,并将字符转为大写。
 * 2. 使用StringBuilder构建格式化的字符串。
 * 3. 通过分组处理每k个字符,插入破折号。
 */
import java.util.stream.Collectors;
import java.util.stream.IntStream;
 
public class LicenseKeyFormattingStream {
    public static String licenseKeyFormatting(String s, int k) {
        // 去掉破折号并转大写
        String cleaned = s.chars()
                .filter(c -> c != '-')
                .mapToObj(c -> Character.toString((char) c).toUpperCase())
                .collect(Collectors.joining());
        StringBuilder sb = new StringBuilder();
        int firstGroupLength = cleaned.length() % k;
        int index = 0;
        // 处理第一个组
        if (firstGroupLength != 0) {
            sb.append(cleaned, 0, firstGroupLength);
            index = firstGroupLength;
        }
        // 处理后续组
        for (int i = index; i < cleaned.length(); i += k) {
            if (sb.length() > 0) sb.append("-");
            sb.append(cleaned, i, Math.min(i + k, cleaned.length()));
        }
        return sb.toString();
    }
}

解释

方法:

这个题解的思路是先将原字符串中的破折号去掉,得到一个只包含字母和数字的字符串。然后计算出第一组的长度,可能会比k短。接着将字符串的第一组转换为大写,作为结果字符串的开头。从第一组之后,每k个字符一组,在它们之前加上破折号,并转换为大写,拼接到结果字符串后面。最终返回重新格式化后的许可密钥字符串。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
解题思路中提到如果字符串长度正好是k的倍数时,第一组也取k个字符,这种情况下第一组是否可以取少于k个字符的其他合法长度?
在这种情况下,第一组取k个字符是为了保持格式化后每组字符的统一性和规整性。如果取少于k个字符的长度,虽然不会影响结果的正确性,但会导致格式化后的密钥第一组与其他组长度不一致,从而降低可读性和美观性。因此,建议即使长度是k的倍数,第一组也应该保持与其他组同样的长度。
🦆
在去除原字符串中的破折号后,直接进行字符串的拼接操作是否会影响性能,尤其是在字符串长度非常大时?
在Python中,字符串是不可变的,因此每次进行字符串拼接时,都会创建一个新的字符串对象,这可能导致内存使用和处理时间上的增加,尤其是在处理非常大的字符串时。为了优化性能,可以考虑使用列表来收集各个部分,最后使用join方法一次性将列表中的字符串合并,这样可以减少内存的重复分配和复制操作,提高效率。
🦆
在进行字符串大写转换时,直接使用str.upper()处理整个子串是否比对每个字符单独转换更有效率?
直接使用str.upper()处理整个子串通常比逐个字符转换更有效率。这是因为str.upper()是高度优化的内置函数,能够在内部实现中利用更低层次的优化和可能的并行处理。对每个字符单独调用大写转换会导致更多的函数调用开销,并可能增加执行时间。
🦆
算法是否支持所有Unicode字母字符的大写转换,还是只支持ASCII范围内的字母?
Python的str.upper()方法支持所有Unicode字母字符的大写转换,不仅限于ASCII范围内的字母。这意味着无论输入字符串中包含的是哪种语言的字母,str.upper()都能正确转换其为大写形式,使得这种转换在全球化应用中非常有用。

相关问题