LeetCode 1544. 整理字符串

2026-05-29 HGNULB 约 6 分钟

文章信息 6 个分类 2 个标签

分类

题目描述

✅ 1544. 整理字符串

题意分析

给定只含英文字母的字符串 s，若相邻两个字符是同一个字母但大小写不同（如 aA 或 Aa），则这两个字符都要删掉。反复执行到不存在这样的相邻对为止，返回最终字符串。题目保证答案唯一。

「答案唯一」这句话是解法的许可证。它意味着删除顺序不影响最终结果，因此不必搜索所有删除次序，可以放心采用一种固定策略——从左到右扫描，一有机会就删。

关键观察在于删除的连锁性：删掉一对字符后，原本被它们隔开的两个字符变成相邻，可能构成新的坏对。例如 "abBA" 删掉中间的 bB 后，a 和 A 相邻，还要继续删。所以不能只扫一遍原串就完事，必须能回头检查刚刚露出来的前一个字符。

「删掉当前元素后要回头看前一个」正是栈的语义：栈顶永远是已保留部分的最后一个字符，恰好是下一个待检字符的左邻居。

边界情况：s 长度为 1 时无相邻对，原样返回；整串可能被删空（如 "abBAcC"），此时返回空字符串。

解法：栈消除相邻坏对

核心思路

模拟做法是反复扫描整个字符串，每轮找到一个坏对就删除并重新开始，最坏 $O(n^2)$。浪费在于：每次删除只影响删除点附近，却重扫了整个字符串。

改用栈一次扫描。维护一个栈保存「已经确定要保留的字符」。对每个新字符 ch：若栈非空且栈顶与 ch 构成坏对，说明两者互相抵消，弹出栈顶且 ch 也不入栈——此时新的栈顶自动成为下一轮的比较对象，连锁删除天然被处理；否则 ch 入栈。

判断坏对有个简洁的位运算技巧：同一字母的大写与小写 ASCII 码恰好相差 32（'a' - 'A' = 32），而 32 是 $2^5$，所以大小写只差在第 5 个二进制位上。于是 (top ^ ch) == 32 一次表达了两个条件——是同一个字母，且大小写不同。若两个字符完全相同，异或结果是 0，不会误删。

正确性依赖一个不变量：每处理完一个字符，栈内相邻元素之间都不构成坏对。因为新字符要么与栈顶抵消（栈缩短，而缩短前栈内本就合法），要么与栈顶不构成坏对才入栈，两种情况都维持了不变量。扫描结束时栈内即为答案。

解题步骤

准备栈：用可变字符序列充当栈。栈底到栈顶就是最终答案的字符顺序，所以扫描结束后直接输出即可，不需要反转。

逐字符扫描：取当前字符 ch，与栈顶比较。

判坏对：栈非空且 (栈顶 ^ ch) == 32。这一步同时覆盖「同字母」与「大小写不同」，写成 Math.abs(栈顶 - ch) == 32 等价。

抵消：构成坏对时弹出栈顶，且 ch 不入栈。不要在这里手动再比一次，交给下一轮循环的栈顶自然处理连锁；本轮已没有待处理字符。

保留：不构成坏对时把 ch 压入栈。

输出：把栈内字符按栈底到栈顶拼成字符串返回，结果可能为空串。

以 s = "leEeetcode" 走一遍（方括号内为栈内容）：l 入栈 [l]；e 入栈 [l,e]；E 与栈顶 e 异或得 32，弹出 e 且 E 丢弃，栈回到 [l]；下一个 e 与栈顶 l 不构成坏对，入栈 [l,e]；再一个 e 与栈顶 e 异或得 0，不是坏对，入栈 [l,e,e]；此后 t、c、o、d、e 依次入栈。结果 "leetcode"。这里第二个 e 与 e 的比较正是「相同字符不能删」的检验点。

再看连锁删除的用例 s = "abBAcC"：a 入栈 [a]；b 入栈 [a,b]；B 与 b 抵消，栈变 [a]；A 与新露出的栈顶 a 抵消，栈变 []；c 入栈 [c]；C 与 c 抵消，栈变 []。返回空串。若用「只扫一遍原串、不回头」的写法，A 会被错误保留。

代码实现

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)$，每个字符最多入栈一次、出栈一次，判断坏对是 $O(1)$。相比反复重扫的 $O(n^2)$ 模拟，省掉的正是「删除后从头再来」那一层。

空间复杂度：$O(n)$，栈最坏保存全部字符（如 "abcd" 没有任何可删对）。返回值本身也需要这个量级，无法更省。

关键点总结

「删除后需要回头检查前一个元素」是栈的典型信号，与括号匹配、相邻重复项消除属于同一模式。

用栈一次扫描能自动处理连锁删除，是因为弹出栈顶后新栈顶立刻成为下一轮的左邻居。

大小写字母的 ASCII 码只差第 5 位，^ 32 可以一次表达「同字母且大小写不同」；异或为 0 天然排除了完全相同的字符。

「答案唯一」的题面保证允许采用固定的贪心删除顺序，不必考虑不同删除次序带来的差异。

易错点总结

判断只比较小写形式：toLowerCase(栈顶) == toLowerCase(ch) 漏掉了「大小写必须不同」，会把 "aa" 也删掉，而正确答案是 "aa"。

误删完全相同的字符：若用 Math.abs(栈顶 - ch) <= 32 这类宽松条件，"ee" 会被错删。判断必须严格等于 32。

只扫一遍原串、不回头：忽略连锁删除，"abBA" 会返回 "aA" 而不是空串。

忘记判空栈：第一个字符就去取栈顶会越界。栈非空的检查必须排在比较之前。

抵消后把当前字符也压入栈：坏对的两个字符都要删掉，当前字符不能保留。

输出时把栈反转：这里栈底到栈顶就是原始顺序，反转会得到逆序字符串。

Java 用字符串拼接代替 StringBuilder：每次删除都产生新对象，退化成 $O(n^2)$。

相似题目

题目	难度	考察点
1047. 删除字符串中的所有相邻重复项	简单	同一模板，判坏对条件换成栈顶与当前字符完全相同
1209. 删除字符串中的所有相邻重复项 II	中等	需删除连续 k 个相同字符，栈元素要额外携带计数
20. 有效的括号	简单	只判定合法性不重建字符串，坏对换成括号配对关系
1003. 检查替换后的词是否有效	中等	消除的是固定子串 `abc`，需要检查栈顶连续两个元素
71. 简化路径	中等	栈元素是路径段而非字符，`..` 触发弹出、`.` 与空段直接忽略