---

1544. 整理字符串

• 标签：栈、字符串
• 难度：简单

题目链接

• 1544. 整理字符串 - 力扣

题目大意

描述：给定一个由大小写字母组成的字符串 $s$。如果一个字符的大写和小写版本相邻（即一个是大写一个是小写），则这两个字符可以消除。

要求：返回反复消除后的最终字符串。

说明：

• $1 \le s.length \le 100$。

示例：

• 示例 1：

输入：s = "leEeetcode"
输出："leetcode"
解释：无论你第一次选的是 i = 1 还是 i = 2，都会使 "leEeetcode" 缩减为 "leetcode" 。

• 示例 2：

输入：s = "abBAcC"
输出：""
解释：存在多种不同情况，但所有的情况都会导致相同的结果。例如：
"abBAcC" --> "aAcC" --> "cC" --> ""
"abBAcC" --> "abBA" --> "aA" --> ""

解题思路

思路 1：栈模拟

1. 核心思想

用栈模拟消除过程。遍历字符串，如果当前字符和栈顶字符互为大小写（即字母相同但大小写不同），则弹出栈顶（消除），否则入栈。

2. 具体步骤

第 1 步：初始化空栈 $stack$。

第 2 步：遍历 $s$ 中的每个字符 $ch$：

• 如果栈非空且 $stack[-1]$ 和 $ch$ 互为大小写（abs(ord(stack[-1]) - ord(ch)) == 32）：弹出栈顶。
• 否则 $ch$ 入栈。

第 3 步：将栈中字符拼接成字符串返回。

3. 互为大小写的判定

小写字母 $a \sim z$ 的 ASCII 码为 $97 \sim 122$，大写字母 $A \sim Z$ 的 ASCII 码为 $65 \sim 90$。同一字母的大小写间差值为 $32$。因此判定条件为：

abs(ord(a) - ord(b)) == 32

或者用 a.swapcase() == b。

4. 举例说明

以 $s = "leEeetcode"$ 为例：

• 入栈 l，入栈 e。
• E 与栈顶 e 互为大小写，弹出 e。
• e 与栈顶 l 不是大小写关系，入栈 e。
• 入栈 e，入栈 t，入栈 c，入栈 o，入栈 d，入栈 e。

结果："leetcode"。

以 $s = "abBAcC"$ 为例：

• 入栈 a，入栈 b。
• B 与 b 消除，栈为 [a]。
• A 与 a 消除，栈为 []。
• c 入栈。
• C 与 c 消除，栈为 []。

结果：""。

思路 1：代码

class Solution:
    def makeGood(self, s: str) -> str:
        stack = []
        for ch in s:
            if stack and abs(ord(stack[-1]) - ord(ch)) == 32:
                stack.pop()
            else:
                stack.append(ch)
        return ''.join(stack)

思路 1：复杂度分析

• 时间复杂度：$O(n)$，一次遍历。
• 空间复杂度：$O(n)$，栈空间。