题目描述

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

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

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

样例

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

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

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

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

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

提示：

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

算法分析

• 1、任意两个相邻字符的类型都不同,开两个队列或者栈或者数组分别存储数字和字母
• 2、有个数多的一方先输出，然后轮流输出直到其中一个队列空为止，最后判断个数多的队列是否为空，若还有一个元素，则继续输出

时间复杂度 $O(n)$

Java 代码

class Solution {
    static String get_ans(Queue<Character> q1,Queue<Character> q2)
    {
        if(q1.size() < q2.size()) return get_ans(q2,q1);
        String ans = "";
        if(q1.size() > q2.size() + 1) return ans; 
        while(!q2.isEmpty())
        {
            ans += q1.poll();
            ans += q2.poll();
        }
        if(!q1.isEmpty()) ans += q1.poll();

        return ans;
    }
    public String reformat(String s) {
        char[] g = s.toCharArray();
        Queue<Character> q1 = new LinkedList<Character>();
        Queue<Character> q2 = new LinkedList<Character>();
        for(int i = 0;i < s.length();i ++)
        {
            if(g[i] >= '0' && g[i] <= '9') q1.add(g[i]);
            else q2.add(g[i]);
        }
        return get_ans(q1,q2);
    }
}