重新格式化字符串

难度: Easy

给你一个混合了数字和字母的字符串 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 <= s.length <= 500
s 仅由小写英文字母和/或数字组成。

Submission

运行时间: 28 ms

内存: 16.8 MB

class Solution:
    def reformat(self, s: str) -> str:
        if len(s) == 1:
            return s
        if s.isalpha():
            return ""
        if s.isdigit():
            return ""
        digits = []
        letters = []
        for char in s:
            if char.isdigit():
                digits.append(char)
            else:
                letters.append(char)
        if abs(len(letters) - len(digits)) > 1:
            return ""
        result = []
        if len(letters) >= len(digits):
            while letters and digits:
                result.append(letters.pop())
                result.append(digits.pop())
            if letters:
                result.append(letters.pop())
        else:
            while letters and digits:
                result.append(digits.pop())
                result.append(letters.pop())
            if digits:
                result.append(digits.pop())

        return "".join(result)

Explain

题目要求将字符串重新格式化，使得任意两个相邻字符的类型都不同（字母和数字交替出现）。首先检查字符串是否只含有一种字符（全部是字母或者全部是数字），如果是，则直接返回空字符串。接着，遍历字符串，将数字和字母分别存储到两个列表中。如果两个列表的长度差大于1，也返回空字符串，因为无法按要求格式化。最后，根据两个列表的长度关系，交替从两个列表中取出元素拼接到结果字符串中，确保较长的列表元素先取。如果有剩余的元素（只会剩下一个），则追加到结果字符串的末尾。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def reformat(self, s: str) -> str:
        if len(s) == 1:
            return s  # 如果字符串长度为1，直接返回
        if s.isalpha():
            return ''  # 如果字符串全是字母，无法格式化
        if s.isdigit():
            return ''  # 如果字符串全是数字，无法格式化
        digits = []  # 用于存储数字
        letters = []  # 用于存储字母
        for char in s:
            if char.isdigit():
                digits.append(char)
            else:
                letters.append(char)
        if abs(len(letters) - len(digits)) > 1:
            return ''  # 字母和数字的数量差距超过1，无法格式化
        result = []
        if len(letters) >= len(digits):
            while letters and digits:
                result.append(letters.pop())  # 弹出并添加一个字母
                result.append(digits.pop())   # 弹出并添加一个数字
            if letters:
                result.append(letters.pop())  # 如果有剩余的字母，添加到结果末尾
        else:
            while letters and digits:
                result.append(digits.pop())  # 同上，先添加数字
                result.append(letters.pop())  # 添加字母
            if digits:
                result.append(digits.pop())  # 如果有剩余的数字，添加到结果末尾

        return ''.join(result)  # 将结果列表转换为字符串并返回

Explore

题目的要求是必须使得新格式化的字符串中任意两个相邻的字符一个是字母，另一个是数字。如果输入字符串只包含字母或者只包含数字，就不可能创建一个符合条件的字符串，因为无法提供必要的交替字符类型。因此，在这种情况下，返回空字符串是表示无法按题目要求格式化的一种明确方式。没有其他可能的输出格式，因为任何包含字符的输出都将违反题目的格式要求。

如果字母和数字的数量差异大于1，意味着无法平衡地交替它们以满足题目的要求。例如，如果有3个字母和1个数字，最多只能形成'字母-数字-字母'的结构，此时还剩一个字母无法与数字交替。因此，当数量差异大于1时，无论如何也无法格式化成符合要求的字符串，所以返回空字符串是避免无效尝试的合理选择。

当字母和数字数量相等时，可以从任一类型开始拼接字符串。可以是'字母-数字'也可以是'数字-字母'，因为无论从哪种类型开始，都可以确保每个字母和数字之间都紧跟着另一种类型的字符。因此，没有严格的顺序要求，可以根据具体情况或者偏好来选择开始的字符类型。

在任意一个类型的列表中剩余元素时，这种情况只能发生当一个列表比另一个列表多一个元素。在这种情况下，剩余的元素总是与最后一个加入结果的元素类型不同。例如，如果字母列表多出一个元素，那么在所有数字已经被交替添加后，最后添加的肯定是数字，因此剩余的字母添加到末尾时，依旧保持了交替的规则。这确保了结果字符串中任意两个相邻字符的类型仍然是不同的。