LeetCode 题解工作台
整理字符串
给你一个由大小写英文字母组成的字符串 s 。 一个整理好的字符串中，两个相邻字符 s[i] 和 s[i+1] ，其中 0 ，要满足如下条件: 若 s[i] 是小写字符，则 s[i+1] 不可以是相同的大写字符。 若 s[i] 是大写字符，则 s[i+1] 不可以是相同的小写字符。 请你将字符串整理好…
2
题型
4
代码语言
3
相关题
当前训练重点
简单 · 栈·状态
答案摘要
时间复杂度 ，空间复杂度 ，其中 是字符串 `s` 的长度。 class Solution:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 栈·状态 题型思路
题目描述
给你一个由大小写英文字母组成的字符串 s 。
一个整理好的字符串中，两个相邻字符 s[i] 和 s[i+1]，其中 0<= i <= s.length-2 ，要满足如下条件:
- 若
s[i]是小写字符，则s[i+1]不可以是相同的大写字符。 - 若
s[i]是大写字符，则s[i+1]不可以是相同的小写字符。
请你将字符串整理好，每次你都可以从字符串中选出满足上述条件的 两个相邻 字符并删除，直到字符串整理好为止。
请返回整理好的 字符串 。题目保证在给出的约束条件下，测试样例对应的答案是唯一的。
注意：空字符串也属于整理好的字符串，尽管其中没有任何字符。
示例 1：
输入：s = "leEeetcode" 输出："leetcode" 解释：无论你第一次选的是 i = 1 还是 i = 2，都会使 "leEeetcode" 缩减为 "leetcode" 。
示例 2：
输入：s = "abBAcC" 输出："" 解释：存在多种不同情况，但所有的情况都会导致相同的结果。例如： "abBAcC" --> "aAcC" --> "cC" --> "" "abBAcC" --> "abBA" --> "aA" --> ""
示例 3：
输入：s = "s" 输出："s"
提示：
1 <= s.length <= 100s只包含小写和大写英文字母
解题思路
方法一：栈模拟
时间复杂度 ，空间复杂度 ，其中 是字符串 s 的长度。
class Solution:
def makeGood(self, s: str) -> str:
stk = []
for c in s:
if not stk or abs(ord(stk[-1]) - ord(c)) != 32:
stk.append(c)
else:
stk.pop()
return "".join(stk)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if the candidate can recognize the stack-based nature of the problem and use it effectively.
- question_mark
Assess whether the candidate can iterate through the string correctly and apply stack operations.
- question_mark
Look for understanding of efficient space usage and time complexity analysis.
常见陷阱
外企场景- error
Failing to handle case sensitivity correctly when checking for cancellations.
- error
Not using a stack and attempting to solve the problem with other data structures that might be inefficient.
- error
Incorrectly constructing the final result from the stack after processing the string.
进阶变体
外企场景- arrow_right_alt
Implement the same solution but track the number of cancellations performed.
- arrow_right_alt
Extend the problem to handle non-adjacent cancellations or more complex cancellation conditions.
- arrow_right_alt
Optimize the solution to handle larger strings or multiple test cases more efficiently.