LeetCode 1417 C++题解：重新格式化字符串

Ruby

发布时间：2026-10-16| 2人浏览过

原创

本文提供 LeetCode 1417 “重新格式化字符串”的 C++ 题解。通过将字母和数字分类统计，确保数量差不超过 1，并利用双指针在偶数位置和奇数位置进行交换，从而实现字母与数字交替排列。若无法满足条件则返回空字符串。

题目描述

给定一个混合了小写英文字母和数字的字符串 s，要求将其重新格式化，使得任意两个相邻字符的类型都不同（即字母后跟数字，或数字后跟字母）。如果无法按要求重新格式化，则返回空字符串。

示例说明：

输入 s = "a0b1c2"，输出可以是 "0a1b2c" 等任意满足条件的字符串。
输入 s = "leetcode"，因全为字母无法区分类型，输出 ""。
输入 s = "1229857369"，因全为数字无法区分类型，输出 ""。

解题思路分析

要使相邻字符类型不同，本质上是让字母和数字交叉排列。这隐含了一个必要条件：字母数量与数字数量之差的绝对值必须小于等于 1。如果两者数量差距超过 1，无论怎么排列，总会出现两个相同类型的字符相邻，此时直接返回空字符串。

当数量差满足条件时，我们可以采用以下策略：

统计字符串中字母（alpha）和数字（digit）的数量。
确定数量较多的字符种类作为“主字符”，数量较少的作为“辅字符”。
将主字符放置在偶数索引位置（0, 2, 4...），辅字符放置在奇数索引位置（1, 3, 5...）。

具体实现步骤

使用双指针思想在原字符串上进行调整，避免额外的空间开销：

初始化：设置两个指针，i 指向偶数位置，j 指向奇数位置。通常令 i=0, j=1。
判断逻辑：我们期望偶数位置上放置的是“主字符”。如果当前 s[i] 不是主字符，则需要从 j 开始寻找第一个属于主字符的位置。
交换元素：找到合适的 j 后，交换 s[i] 和 s[j] 的值。
遍历完成：每次 i 增加 2，直到遍历完所有可能的偶数位置。由于数量差 ≤ 1，这种策略能保证构造成功。

在代码优化中，可以通过布尔变量 f（表示数字是否多于字母）来简化判断。例如用 isdigit(s[i]) != f 这一句语句即可涵盖两种情况的判断：

若 f=true（数字多），期望偶数位是数字。若 isdigit(s[i]) 为假（是字母），则需替换。
若 f=false（字母多），期望偶数位是字母。若 isdigit(s[i]) 为真（是数字），则需替换。

复杂度分析

时间复杂度：O(n)，其中 n 是字符串长度。我们需要遍历字符串统计次数，以及通过双指针再次遍历进行交换，整体线性时间。
空间复杂度：O(1)，仅使用了几个整型变量和指针，无需额外存储空间（字符串本身可修改）。

C++ 代码实现

class Solution {
public:
    string reformat(string s) {
        // 统计数字和字母的个数
        int sum_digit = 0, sum_alpha = 0;
        for(auto &c : s){
            if(isdigit(c)) sum_digit++;
            else sum_alpha++;
        }
        // 当个数差大于 1 时无法构造
        if(abs(sum_digit - sum_alpha) > 1) return "";
        
        bool f = sum_digit > sum_alpha;
        int n = s.size();
        
        // 双指针 i 指向偶数位，j 指向奇数位
        for(int i = 0, j = 1; i < n; i += 2){
            // 如果当前位置字符不符合预期（预期偶数位放多数类字符）
            if(isdigit(s[i]) != f){
                // 从奇数位寻找符合预期的字符
                while(isdigit(s[j]) != f) j += 2;
                swap(s[i], s[j]);
            }
        }
        return s;
    }
};