Easy

题目描述

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

解题思路

解题思路

这道题的核心是判断能否交替排列字母和数字。

分析可行性： 首先统计字符串中字母和数字的数量。要实现交替排列，两种字符的数量差不能超过1，即：

  • 如果 |字母数 - 数字数| ≤ 1，则可以重新格式化
  • 如果差值大于1，则无法实现交替排列

构造策略：

  1. 将字符串分为两组：字母组和数字组
  2. 确定起始字符类型：数量较多的那种类型先放
  3. 交替放置两种类型的字符

实现步骤：

  1. 遍历字符串，分别收集字母和数字
  2. 判断是否可以重新格式化（数量差不超过1）
  3. 确定哪种字符应该放在奇数位置（数量多的）
  4. 按位置交替填充结果字符串

时间复杂度O(n)，空间复杂度O(n)，其中n是字符串长度。

代码实现

class Solution {
public:
    string reformat(string s) {
        vector<char> letters, digits;
        
        // 分离字母和数字
        for (char c : s) {
            if (isalpha(c)) {
                letters.push_back(c);
            } else {
                digits.push_back(c);
            }
        }
        
        // 检查是否可能重新格式化
        if (abs((int)letters.size() - (int)digits.size()) > 1) {
            return "";
        }
        
        // 确定哪种字符先放（数量多的先放）
        vector<char>& first = letters.size() > digits.size() ? letters : digits;
        vector<char>& second = letters.size() > digits.size() ? digits : letters;
        
        string result(s.length(), ' ');
        int idx = 0;
        
        // 先放数量多的字符类型
        for (char c : first) {
            result[idx] = c;
            idx += 2;
        }
        
        // 再放数量少的字符类型
        idx = 1;
        for (char c : second) {
            result[idx] = c;
            idx += 2;
        }
        
        return result;
    }
};

class Solution:
    def reformat(self, s: str) -> str:
        letters = []
        digits = []
        
        # 分离字母和数字
        for c in s:
            if c.isalpha():
                letters.append(c)
            else:
                digits.append(c)
        
        # 检查是否可能重新格式化
        if abs(len(letters) - len(digits)) > 1:
            return ""
        
        # 确定哪种字符先放（数量多的先放）
        if len(letters) > len(digits):
            first, second = letters, digits
        else:
            first, second = digits, letters
        
        result = [''] * len(s)
        
        # 先放数量多的字符类型
        idx = 0
        for c in first:
            result[idx] = c
            idx += 2
        
        # 再放数量少的字符类型
        idx = 1
        for c in second:
            result[idx] = c
            idx += 2
        
        return ''.join(result)

public class Solution {
    public string Reformat(string s) {
        var letters = new List<char>();
        var digits = new List<char>();
        
        // 分离字母和数字
        foreach (char c in s) {
            if (char.IsLetter(c)) {
                letters.Add(c);
            } else {
                digits.Add(c);
            }
        }
        
        // 检查是否可能重新格式化
        if (Math.Abs(letters.Count - digits.Count) > 1) {
            return "";
        }
        
        // 确定哪种字符先放（数量多的先放）
        var first = letters.Count > digits.Count ? letters : digits;
        var second = letters.Count > digits.Count ? digits : letters;
        
        var result = new char[s.Length];
        int idx = 0;
        
        // 先放数量多的字符类型
        foreach (char c in first) {
            result[idx] = c;
            idx += 2;
        }
        
        // 再放数量少的字符类型
        idx = 1;
        foreach (char c in second) {
            result[idx] = c;
            idx += 2;
        }
        
        return new string(result);
    }
}

var reformat = function(s) {
    const letters = [];
    const digits = [];
    
    // 分离字母和数字
    for (let c of s) {
        if (c >= 'a' && c <= 'z') {
            letters.push(c);
        } else {
            digits.push(c);
        }
    }
    
    // 检查是否可能重新格式化
    if (Math.abs(letters.length - digits.length) > 1) {
        return "";
    }
    
    // 确定哪种字符先放（数量多的先放）
    const first = letters.length > digits.length ? letters : digits;
    const second = letters.length > digits.length ? digits : letters;
    
    const result = new Array(s.length);
    let idx = 0;
    
    // 先放数量多的字符类型
    for (let c of first) {
        result[idx] = c;
        idx += 2;
    }
    
    // 再放数量少的字符类型
    idx = 1;
    for (let c of second) {
        result[idx] = c;
        idx += 2;
    }
    
    return result.join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串一次进行分类，再遍历一次构造结果
空间复杂度O(n)需要额外空间存储分类后的字符和结果字符串