0482. License Key Formatting ============================ 题目信息 -------- :题号: 0482 :难度: Easy :主题: 字母数字字符串、删除连字符、从右分组、大写格式 :原题: `LeetCode 0482 `_ :重点: 忽略原有连字符、除首组外每组恰好 ``k`` 个字符、首组可短、所有字母转大写 题目重述 -------- 给定由英文字母、数字和连字符组成的许可证字符串 ``s``,以及正整数 ``k``。先删除全部原有连字符并把字母转换为大写,再用连字符把字符重新分组。 除第一组外,每组必须恰好包含 ``k`` 个字符;第一组长度可以小于 ``k``,但必须至少为 1。分组方向等价于从字符串末尾向前每 ``k`` 个字符切一组。``s.length`` 位于 ``[1, 10^5]``,``k`` 位于 ``[1, 10^4]``,输入保证至少包含一个字母或数字。 自建示例 -------- 首组比其他组短: .. code-block:: text 输入:s = "a-bC-dEf-gh",k = 3 输出:"AB-CDE-FGH" 解释:删除连字符得到 abcdefgh,从右侧按三字符分组为 ab、cde、fgh,再统一转成大写。 每个字符单独成组: .. code-block:: text 输入:s = "2-z",k = 1 输出:"2-Z" 解释:删除原连字符后每个字符组成一组,字母 z 转为大写 Z。 清洗后从右侧切分 ---------------- 先删除所有原有连字符并统一大小写,得到连续字符序列。分组时从末尾向左每次取 ``k`` 个字符,最后剩下的前缀自然成为首组;若总长度能被 ``k`` 整除,首组长度就是 ``k``,不会产生空组。 从左侧按首组长度输出也可以保持顺序,同时避免反复在字符串头部插入导致线性移动。 C++ 实现 -------- .. code-block:: cpp class Solution { public: std::string licenseKeyFormatting(std::string s, int k) { std::string clean; for (char character : s) { if (character == '-') continue; clean.push_back(static_cast(std::toupper( static_cast(character)))); } int firstLength = clean.size() % k; if (firstLength == 0) firstLength = k; std::string result = clean.substr(0, firstLength); for (int begin = firstLength; begin < static_cast(clean.size()); begin += k) { result.push_back('-'); result.append(clean, begin, k); } return result; } }; 代码分析 -------- 首组长度由除法余数决定,之后每段固定取 ``k`` 个字符,正好对应从右向左分组的结果;原有连字符从未进入 ``clean``,所以不会影响新边界。清洗和生成各扫描一次,时间复杂度为 ``O(|s|)``,额外空间复杂度为 ``O(|s|)``。