整理字符串

标签: 栈字符串

难度: Easy

给你一个由大小写英文字母组成的字符串 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 <= 100
s 只包含小写和大写英文字母

Submission

运行时间: 27 ms

内存: 16.0 MB

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

Explain

此题解采用栈的数据结构来处理字符串的整理问题。遍历输入字符串s的每个字符，使用栈来暂存待判定的字符。对于每个字符，检查栈顶元素是否与当前字符相邻且大小写不同（ASCII值差32表示字符大小写之间的转换），如果是，则弹出栈顶元素表示两个字符相互抵消；如果不是，则将当前字符压入栈中。最终栈中剩余的字符序列即为整理后的字符串，因为所有可以相互抵消的字符都已被移除。遍历完成后，将栈中的字符连接成字符串作为结果返回。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def makeGood(self, s: str) -> str:
        stack = []  # 使用栈来存储未处理的字符
        for i in s:
            if stack and abs(ord(stack[-1]) - ord(i)) == 32:
                # 如果栈非空且栈顶字符与当前字符是大小写不同的同一字母，则弹出栈顶
                stack.pop()
            else:
                # 否则，将当前字符压入栈中
                stack.append(i)
        return ''.join(stack)  # 将栈中剩余的字符连接成字符串后返回

Explore

在ASCII编码中，大小写字母之间的差异正好是32。例如，'A'的ASCII码为65而'a'的ASCII码为97，二者的差为32。这一规则适用于所有的英文字母。因此，如果两个字符的ASCII值差为32，就可以确定这两个字符是同一个字母的大小写不同形式。这种方法是一种快速而有效的方式来检查两个字符是否应该在处理过程中被消除。

如果输入字符串已经是整理好的，算法将遍历整个字符串，并将每个字符依次压入栈中，因为没有任何字符可以与之前的字符抵消。在这种情况下，算法的时间复杂度是O(n)，其中n是字符串的长度。栈操作包括对每个字符执行一次压栈操作，没有弹出操作。这表示栈的最大大小将与输入字符串的长度相同。

如果输入是空字符串，那么在算法的执行过程中，栈将始终保持为空。遍历字符串的循环将直接跳过，因为没有字符需要处理。最终，算法将返回一个空字符串。这种情况下，算法的处理非常直接且效率很高，因为它实际上没有进行任何操作。

在算法处理过程中使用栈是为了方便进行字符的消除操作，因为栈提供了便捷的后进先出（LIFO）特性，使得最近添加的字符可以快速被移除。如果在处理过程中直接构建最终字符串，一旦遇到需要消除的字符对，修改已构建的字符串部分将更加复杂和耗时。因此，使用栈来处理字符，然后在所有操作完成后将结果转换为字符串，是一种更有效和清晰的方法。