How do I handle strings with only letters or only digits in Reformat The String?

In such cases, immediately return an empty string because no valid reformatting is possible without the presence of both letters and digits.

What is the time complexity of the solution for Reformat The String?

The time complexity is O(n), where n is the length of the string, due to the need to traverse the string and count characters.

Can I solve Reformat The String using recursion?

While recursion could be applied, an iterative approach is generally more efficient for this problem and avoids the potential overhead of recursive calls.

How do I know when the reformatting is impossible in Reformat The String?

Reformatting is impossible if the difference in counts between letters and digits exceeds 1, meaning you can't alternate them without two of the same type being adjacent.

What should be the approach when the counts of letters and digits are the same in Reformat The String?

When the counts are the same, you can start the reformatting with either letters or digits. The result will alternate successfully between the two types.

#1417

Easy

auto_awesomeString-driven solution strategy

LeetCode 题解工作台

重新格式化字符串

给你一个混合了数字和字母的字符串 s ，其中的字母均为小写英文字母。请你将该字符串重新格式化，使得任意两个相邻字符的类型都不同。也就是说，字母后面应该跟着数字，而数字后面应该跟着字母。请你返回重新格式化后的字符串；如果无法按要求重新格式化，则返回一个空字符串。示例 1：输入： s =…

字符串

题目描述

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

lightbulb

解题思路

方法一：模拟

将字符串 $s$ 中的所有字符分成“数字”、“字母”两类，分别放入 $a$ , $b$ 两个数组中。

比较 $a$ , $b$ 两个数组的长度，若 $a$ 长度小于 $b$ ，则交换 $a$ , $b$ 。接着判断两个数组长度差，若超过 $1$ ，则返回空字符串。

接着同时遍历两个数组，依次添加 $a$ , $b$ 中对应字符到答案中。遍历结束，若 $a$ 长度大于 $b$ ，则添加 $a$ 的最后一个字符到答案中。

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def reformat(self, s: str) -> str:
        a = [c for c in s if c.islower()]
        b = [c for c in s if c.isdigit()]
        if abs(len(a) - len(b)) > 1:
            return ''
        if len(a) < len(b):
            a, b = b, a
        ans = []
        for x, y in zip(a, b):
            ans.append(x + y)
        if len(a) > len(b):
            ans.append(a[-1])
        return ''.join(ans)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Focus on whether the candidate can identify edge cases like strings containing only letters or digits.
question_mark
Evaluate their understanding of string-driven solution strategies and balancing character types.
question_mark
Check if they are able to explain the time and space complexities clearly and concisely.

warning

常见陷阱

外企场景

error
Forgetting to handle edge cases where there are no letters or no digits, leading to incorrect answers.
error
Incorrectly assuming that the order of characters doesn't matter in terms of type adjacency.
error
Not considering cases where the counts of letters and digits differ by more than 1, leading to wrong results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handling strings with a mix of uppercase and lowercase letters.
arrow_right_alt
Optimizing the solution for very large strings close to the maximum input size.
arrow_right_alt
Allowing spaces or other characters in the input string.

help

常见问题

外企场景

继续练习

#1416 恢复数组 #1418 点菜展示表 #1415 长度为 n 的开心字符串中字典序第 k 小的字符串