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 只包含大小写英文字母

解题思路

解题思路

这道题的核心是要删除相邻的大小写字母对，直到没有这样的对存在。我们可以用栈来解决这个问题。

栈解法（推荐）

遍历字符串中的每个字符：

  1. 如果栈为空，直接将字符入栈
  2. 如果栈不为空，检查当前字符与栈顶字符是否构成大小写字母对
    • 判断条件：两个字符不相同且转换为小写后相同
    • 如果是字母对，弹出栈顶元素（相当于删除这一对字符）
    • 如果不是字母对，将当前字符入栈

最后栈中剩余的字符就是整理后的字符串。

其他解法

也可以使用双指针或者递归的方式，但栈解法最直观且效率最高。

时间复杂度： O(n)，每个字符最多入栈和出栈一次
空间复杂度： O(n)，栈的空间

代码实现

class Solution {
public:
    string makeGood(string s) {
        string stack;
        for (char c : s) {
            if (!stack.empty() && stack.back() != c && 
                tolower(stack.back()) == tolower(c)) {
                stack.pop_back();
            } else {
                stack.push_back(c);
            }
        }
        return stack;
    }
};

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

public class Solution {
    public string MakeGood(string s) {
        var stack = new List<char>();
        foreach (char c in s) {
            if (stack.Count > 0 && stack[stack.Count - 1] != c && 
                char.ToLower(stack[stack.Count - 1]) == char.ToLower(c)) {
                stack.RemoveAt(stack.Count - 1);
            } else {
                stack.Add(c);
            }
        }
        return new string(stack.ToArray());
    }
}

var makeGood = function(s) {
    let stack = [];
    
    for (let char of s) {
        if (stack.length > 0 && 
            stack[stack.length - 1].toLowerCase() === char.toLowerCase() &&
            stack[stack.length - 1] !== char) {
            stack.pop();
        } else {
            stack.push(char);
        }
    }
    
    return stack.join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)遍历字符串一次，每个字符最多入栈出栈各一次
空间复杂度O(n)最坏情况下栈中存储所有字符