Easy

题目描述

给你一个由数字和字母以及破折号组成的字符串 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 被分成了三部分，每部分有 2 个字符，除了第一部分，因为它可以更短，如上所述。

提示：

  • 1 <= s.length <= 10^5
  • s 由英文字母、数字和破折号 '-' 组成
  • 1 <= k <= 10^4

解题思路

这是一道字符串处理问题，核心思路是从右向左组织字符。

解题思路：

  1. 预处理：首先去除所有破折号，并将所有字母转为大写
  2. 从右向左分组：从处理后的字符串末尾开始，每 k 个字符为一组
  3. 构建结果：将分组用破折号连接，注意第一组可能不足 k 个字符

关键点：

  • 从右向左处理可以确保除第一组外，其他组都恰好有 k 个字符
  • 使用栈或逆序处理来构建最终结果
  • 需要特别处理边界情况（如空字符串、只有破折号等）

算法步骤：

  1. 遍历原字符串，跳过破折号，收集有效字符并转大写
  2. 从收集到的字符末尾开始，每 k 个字符插入一个破折号
  3. 将结果逆序得到最终答案

这种从右向左的处理方式确保了分组的正确性，避免了复杂的长度计算。

代码实现

class Solution {
public:
    string licenseKeyFormatting(string s, int k) {
        string chars;
        // 收集所有有效字符并转大写
        for (char c : s) {
            if (c != '-') {
                chars += toupper(c);
            }
        }
        
        if (chars.empty()) return "";
        
        string result;
        int count = 0;
        
        // 从右向左处理
        for (int i = chars.length() - 1; i >= 0; i--) {
            if (count == k) {
                result += '-';
                count = 0;
            }
            result += chars[i];
            count++;
        }
        
        // 结果是逆序的，需要反转
        reverse(result.begin(), result.end());
        return result;
    }
};

class Solution:
    def licenseKeyFormatting(self, s: str, k: int) -> str:
        # 去除破折号并转大写
        chars = ''.join(c.upper() for c in s if c != '-')
        
        if not chars:
            return ""
        
        result = []
        count = 0
        
        # 从右向左处理
        for i in range(len(chars) - 1, -1, -1):
            if count == k:
                result.append('-')
                count = 0
            result.append(chars[i])
            count += 1
        
        # 结果是逆序的，需要反转
        return ''.join(reversed(result))

public class Solution {
    public string LicenseKeyFormatting(string s, int k) {
        StringBuilder chars = new StringBuilder();
        
        // 收集所有有效字符并转大写
        foreach (char c in s) {
            if (c != '-') {
                chars.Append(char.ToUpper(c));
            }
        }
        
        if (chars.Length == 0) return "";
        
        StringBuilder result = new StringBuilder();
        int count = 0;
        
        // 从右向左处理
        for (int i = chars.Length - 1; i >= 0; i--) {
            if (count == k) {
                result.Append('-');
                count = 0;
            }
            result.Append(chars[i]);
            count++;
        }
        
        // 结果是逆序的，需要反转
        char[] arr = result.ToString().ToCharArray();
        Array.Reverse(arr);
        return new string(arr);
    }
}

var licenseKeyFormatting = function(s, k) {
    let cleaned = s.replace(/-/g, '').toUpperCase();
    if (cleaned.length === 0) return '';
    
    let result = [];
    let count = 0;
    
    for (let i = cleaned.length - 1; i >= 0; i--) {
        if (count === k) {
            result.unshift('-');
            count = 0;
        }
        result.unshift(cleaned[i]);
        count++;
    }
    
    return result.join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串两次，n为字符串长度
空间复杂度O(n)需要额外空间存储处理后的字符和结果