LeetCode 1417. 重新格式化字符串

约 5 分钟
文章信息 6 个分类 1 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 字节
标签
字符串

题目描述

✅ 1417. 重新格式化字符串

image-20260929082543036

image-20260929082543134

题意分析

输入只含小写英文字母和数字，需要重新排列全部字符，使相邻两位的类型不同，也就是字母与数字严格交替。允许任意合法排列，不要求保持原顺序。

每个原字符都必须恰好保留一次，不能为了满足交替而删掉某些字符。无法安排时返回空字符串；判断的是字符类型，不是两个相邻字符的值是否相同。

解法：两组缓冲交替拼接

核心思路

[!blue]

先将字符分为字母组和数字组。交替序列每两个位置各使用一种类型，只有最后可能多出一个首类型，因此两组数量差不能超过一；数量差更大就不可能容纳全部字符。

这个条件也足够：两组等长时任选一种开头，轮流各放一个即可；某组多一个时，让它开头和结尾，仍然轮流放置，就能把所有字符都用完。

代码将较长组统一命名为 first，另一组为 second。遍历 first，每次先追加它的当前字符，再在 second 还有对应位置时追加另一个字符。因为长度差最多一，second 只可能在最后一轮耗尽，不会在中途破坏交替。

两个分组缓冲保留各自内部的原顺序，虽然题目不强制这一点，但这样直接依次读取就能保证不丢字符、不重复使用。每个字符进入对应组一次、再进入结果一次，构造完成后自然满足全部约束。

解题步骤

  1. 扫描字符串，按类型分别放入字母缓冲和数字缓冲。
  2. 两组数量差大于一时，返回空字符串。
  3. 令较长组为 first，较短组为 second，等长时任选。
  4. 遍历 first，先放一个首类型字符，有对应项时再放一个另一类型字符。
  5. 返回完整结果，多数类若多一个就自然留在最后。

代码实现

class Solution {
    public String reformat(String s) {
        StringBuilder letters = new StringBuilder();
        StringBuilder digits = new StringBuilder();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (c >= '0' && c <= '9') {
                digits.append(c);
            } else {
                letters.append(c);
            }
        }

        // 交替序列的两类数量最多相差一。
        if (Math.abs(letters.length() - digits.length()) > 1) {
            return "";
        }

        StringBuilder first = letters;
        StringBuilder second = digits;

        // 数量较多的一类必须先放，统一成 first 和 second。
        if (digits.length() > letters.length()) {
            first = digits;
            second = letters;
        }

        StringBuilder answer = new StringBuilder(s.length());

        for (int i = 0; i < first.length(); i++) {
            answer.append(first.charAt(i));

            // 短组只可能在最后耗尽，保留多数类最后一个字符。
            if (i < second.length()) {
                answer.append(second.charAt(i));
            }
        }

        return answer.toString();
    }
}

func reformat(s string) string {
    letters := make([]byte, 0)
    digits := make([]byte, 0)
    for i := 0; i < len(s); i++ {
        if s[i] >= '0' && s[i] <= '9' {
            digits = append(digits, s[i])
        } else {
            letters = append(letters, s[i])
        }
    }

    // 交替序列的两类数量最多相差一。
    if len(letters)-len(digits) > 1 || len(digits)-len(letters) > 1 {
        return ""
    }

    first, second := letters, digits
    // 数量较多的一类必须先放，统一成 first 和 second。
    if len(digits) > len(letters) {
        first, second = digits, letters
    }

    answer := make([]byte, 0, len(s))
    for i := 0; i < len(first); i++ {
        answer = append(answer, first[i])
        // 短组只可能在最后耗尽，保留多数类最后一个字符。
        if i < len(second) {
            answer = append(answer, second[i])
        }
    }
    return string(answer)
}

复杂度分析

设字符串长度为 $n$。

  • 时间复杂度：$O(n)$，分组和构造各扫描一次全部字符。
  • 辅助空间复杂度：$O(n)$，两个分组缓冲合计保存全部字符，构造结果也需要线性空间。

关键点总结

[!green]

  • 数量差不超过一，是全部字符能够交替的充要条件。
  • 多数类型必须放在首尾，等长时两种开头都可行。
  • 遍历长组并按需插入短组，自动处理末尾多出的一个字符。

易错点总结

[!yellow]

  • 固定让字母开头，会在数字多一个时无法安排完所有字符。
  • 只允许两组等长，会拒绝差一个以及单字符的合法输入。
  • 只遍历短组，会遗漏多数类最后的一个字符。
  • 只检查一个方向的差值，会漏掉另一类型过多的无解情况。
  • 相邻字母即使互不相同也不合法，要求交替的是类型。

相似题目

题目 难度 关联与区别
922. 按奇偶排序数组 II 简单 同样把两类元素交替放入不同位置，本题两类数量可相差1，需要让较多的一类先放。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/84636525
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！