LeetCode 1544. 整理字符串
题目描述
题意分析
反复删除相邻且属于同一字母、大小写相反的两个字符，直到不存在这样的字符对。保留字符的相对顺序不变，结果可以为空；题目保证最终结果唯一。
解法：栈式抵消
核心思路
[!blue]
从左到右处理字符，用栈保存已扫描前缀经过合法删除后的结果，并保持栈内不存在可删除的相邻对。开始时栈为空，这个性质自然成立。
新字符加入时，栈内原有相邻关系都没变化，唯一可能新出现的坏对是“栈顶与当前字符”。若两者能抵消，弹出栈顶，并且不把当前字符入栈；剩下的仍是原来已整理好的栈前缀。如果不能抵消，就把当前字符压栈，新形成的相邻对也合法。因此每一步都能维持栈已经整理好的性质。
抵消后当前字符也已经消失，不需要用同一个字符继续匹配新栈顶。后面的输入会与删减后暴露出的栈顶比较，于是后续产生的连锁抵消也能自然发生，不必反复扫描或在原字符串中移动中间字符。
输入只含英文字母，同一字母的大小写编码只相差值为 32 的那一位，所以两字符异或等于 32，恰好表示它们属于同一字母且大小写相反。相同大小写的相同字符异或为零，不会被删除。扫描完成后，栈就是一个已无法继续删除的合法结果，按栈底到栈顶顺序返回即可。
解题步骤
- 建立空栈，逐个读取输入字符。
- 栈非空且栈顶与当前字符异或为 32 时，弹出栈顶并丢弃当前字符。
- 其他情况将当前字符追加到栈顶。
- 所有字符处理完后，直接返回栈中保留的字符串，不反转顺序。
代码实现
class Solution {
public String makeGood(String s) {
StringBuilder stack = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
int top = stack.length() - 1;
// 同一字母的大小写 ASCII 码恰好相差 32，异或结果为 32；完全相同则为 0。
if (top >= 0 && (stack.charAt(top) ^ ch) == 32) {
stack.deleteCharAt(top);
} else {
stack.append(ch);
}
}
return stack.toString();
}
}
func makeGood(s string) string {
stack := make([]byte, 0, len(s))
for i := 0; i < len(s); i++ {
ch := s[i]
// 同一字母的大小写 ASCII 码恰好相差 32，异或结果为 32；完全相同则为 0。
if n := len(stack); n > 0 && stack[n-1]^ch == 32 {
stack = stack[:n-1]
} else {
stack = append(stack, ch)
}
}
return string(stack)
}
复杂度分析
- 时间复杂度：$O(n)$。每个字符最多入栈、出栈各一次；Java 删除的是
StringBuilder的最后一个字符，不需要移动后续字符。- 空间复杂度：$O(n)$，最坏所有字符都保留在栈中。
关键点总结
[!green]
- 栈顶是当前字符左边仍然有效的相邻字符。
- 只检查新字符与栈顶，就能维持已扫描前缀始终整理完毕。
- 一次抵消删除两个字符，当前字符不再继续参与后续比较。
易错点总结
[!yellow]
- 只比较转小写后是否相同，会误删大小写也相同的字符对。
- 只删除原串第一轮出现的坏对，可能留下删除后新形成的坏对。
- 弹出栈顶后仍压入当前字符，只删除了一半。
- 栈按扫描顺序保存结果，输出时反转会破坏剩余字符的相对顺序。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1047. 删除字符串中的所有相邻重复项 | 简单 | 栈式消除相同，本题删除同字母异大小写的相邻对，原题删除完全相同字符。 |
| 2390. 从字符串中移除星号 | 中等 | 同样用栈保留尚未消除的前缀，触发规则不同。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！