C C++ 重新格式化字符串

题目描述

题目链接：1417. 重新格式化字符串

给你一个混合了数字和字母的字符串 s，其中的字母均为小写英文字母。

请你将该字符串重新格式化，使得任意两个相邻字符的类型都不同。也就是说，字母后面应该跟着数字，而数字后面应该跟着字母。

请你返回 重新格式化后 的字符串；如果无法按要求重新格式化，则返回一个 空字符串 。

提示:

• 1⩽s.length⩽5001 
• s 仅由小写英文字母和/或数字组成。

示例 1：

输入：s = "a0b1c2"
输出："0a1b2c"
解释："0a1b2c" 中任意两个相邻字符的类型都不同。 "a0b1c2", "0a1b2c", "0c2a1b" 也是满足题目要求的答案。

示例 2：

输入： s = "leetcode"
输出： ""
解释： "leetcode" 中只有字母，所以无法满足重新格式化的条件。

示例 3：

输入： s = "1229857369"
输出： ""
解释： "1229857369" 中只有数字，所以无法满足重新格式化的条件。

示例 4：

输入： s = "covid2019"
输出： "c2o0v1i9d"

示例 5：

输入： s = "ab123"
输出： "1a2b3"

整理题意

题目给定一个字符串，仅包含小写字母和数字，让我们利用字符串中所给的这些字符构造一个字符串，使得构造出来的字符串中字母字符和数字字符不相邻。答案返回任意一个满足条件的字符串即可，如果无法构造这样的字符串返回空字符串。

解题思路分析

根据题目描述可知，为了使得字符串中不含有相邻的字母和数字，我们尽可能的使得字母和数字交叉排列，那么当字符串中数字个数和字母个数的差值大于 1 时，无论我们怎么排列总会有两个相同的字母字符或数字字符相邻。

那么考虑当字符串中数字个数和字母个数的差值小于等于 1 时，我们将个数较多的种类字符放在偶数位置上，较少的字符种类放在奇数位置上（位置从 0 开始）。

具体实现

首先统计字符串中数字字符个数和字母字符个数，并判断两者差值是否大于 1，大于 1 的情况直接返回空字符串。

双指针 实现字符串排列：

• 指针 i 指向偶数位置，j 指向奇数位置；
• 初始化 i = 0， j = 1；
• 当 i 位置上的字符不为较多的字符种类时，利用 j 指针从左到右找到第一个较多的字符种类，与位置 i 进行交换字符；
• 重复步骤 3 直至遍历完整个字符串。

细节操作：代码实现过程中仅用 if(isdigit(s[i]) != f) 这样的判断语句涵括了两种情况的判断。

复杂度分析

• 时间复杂度：O(n)，其中 n 为字符串 s 的长度，需要遍历两遍字符串。
• 空间复杂度：O(1)，仅使用常量空间。

代码实现

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();
        for(int i = 0, j = 1; i < n; i += 2){
            // 注意判断语句的难点，和 f 有关
            if(isdigit(s[i]) != f){
                while(isdigit(s[j]) != f) j += 2;
                swap(s[i], s[j]);
            }
        }
        return s;
    }
};

总结

• 该题为简单的字符串题目，需要注意的是代码实现过程中的判断语句部分，isdigit(s[i]) != f 这样一句判断语句即可涵括两种情况的判断，且判断语句需要根据 f 的定义来写。
• 另外就是双指针的思想，巧妙利用双指针实现字符串的原地构造。
• 测试结果：