20.有效的括号

LeetCode LeetCode 热题100 字符串 栈
发布时间 :
字数:4.5k 阅读 : 评论:
  1. 20.有效的括号
    1. 20.1 题目
    2. 20.2 题解
      1. 方法一：列表装左括号对比
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：双栈弹出括号验证
        1. 思路
        2. 复杂度分析
        3. 代码
      3. 方法三：单栈弹出括号验证
        1. 思路
        2. 复杂度分析
        3. 代码
      4. 方法四：使用字典和栈验证括号
        1. 思路
        2. 复杂度分析
        3. 代码
    3. 20.3 代码
    4. 20.4 运行结果

20.有效的括号

20.1 题目

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例：

  • 示例 1：

    • 输入：s = "()"
    • 输出：true

  • 示例 2：

    • 输入：s = "()[]{}"
    • 输出：true

  • 示例 3：

    • 输入：s = "(]"
    • 输出：false

提示：

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成

20.2 题解

方法一：列表装左括号对比

思路

遍历字符串，遇到左括号就加入列表，遇到右括号就检查列表末尾是否有匹配的左括号。如果匹配则移除，否则返回 false。最终列表为空则有效。

具体步骤：

  1. 先检查字符串长度是否为偶数，奇数长度直接返回 false。
  2. 遍历字符串每个字符：
    • 如果是左括号 (、{、[，加入列表。
    • 如果是右括号，检查列表末尾是否有对应的左括号：
      • 有则移除列表末尾元素（匹配成功）
      • 没有则返回 false（匹配失败）
  3. 最终检查列表是否为空，为空则所有括号都匹配成功。

举例：对于字符串 ()[]{}：

  • 遇到 (，列表：[(]
  • 遇到 )，匹配列表末尾 (，移除，列表：[]
  • 遇到 [，列表：[[]
  • 遇到 ]，匹配列表末尾 [，移除，列表：[]
  • 遇到 {，列表：[{]
  • 遇到 }，匹配列表末尾 {，移除，列表：[]
  • 最终列表为空，返回 true。

复杂度分析

  • 时间复杂度：O(n)，遍历一次字符串。
  • 空间复杂度：O(n)，最坏情况下列表存储所有左括号。

代码

// 方法一：列表装左括号对比
// 遍历字符串，是左括号就丢到列表里，是右括号的话就判断和列表尾部括号是否匹配
static bool IsValid1(string s)
{
    // 检查字符串长度是否为偶数，奇数长度的字符串无法满足括号闭合条件
    if (s.Length % 2 != 0) return false;

    // 用于存储左括号的列表
    List<char> leftBracketList = new List<char>();

    // 遍历输入字符串的每个字符
    for (int i = 0; i < s.Length; i++)
    {
        // 调用 ReturnLeftBracket 函数获取与当前右括号相匹配的左括号
        char leftBracket = ReturnLeftBracket(s[i]);

        // 如果返回的左括号不为空格，说明当前字符是右括号
        if (leftBracket != ' ')
        {
            // 检查 leftBracketList 中是否有左括号与当前右括号匹配
            if (leftBracketList.Count > 0 && leftBracketList[leftBracketList.Count - 1] == leftBracket)
            {
                // 如果匹配成功，移除 leftBracketList 中的匹配左括号
                leftBracketList.RemoveAt(leftBracketList.Count - 1);
            }
            else
            {
                // 如果匹配失败，说明括号闭合顺序不正确，返回 false
                return false;
            }
        }
        else
        {
            // 如果返回的左括号为空格，说明当前字符是左括号，将其添加到 leftBracketList 中
            leftBracketList.Add(s[i]);
        }
    }

    // 最终检查 leftBracketList 是否为空，若为空，则括号闭合成功，返回 true；否则，返回 false
    return leftBracketList.Count == 0;
}

// 根据右括号返回相应的左括号
static char ReturnLeftBracket(char rightBracket)
{
    switch (rightBracket)
    {
        case ')':
            return '(';
        case '}':
            return '{';
        case ']':
            return '[';
        default:
            return ' '; // 如果输入的不是右括号，则返回空格表示不匹配
    }
}

方法二：双栈弹出括号验证

思路

先将所有字符压入一个栈，然后依次弹出。遇到右括号压入右括号栈，遇到左括号则检查右括号栈顶是否匹配。这种方法从后向前处理。

具体步骤：

  1. 先检查字符串长度是否为偶数。
  2. 将所有字符压入 bracketPushStack 栈。
  3. 从栈中依次弹出字符：
    • 如果是右括号，压入 rightBracketPopStack 栈。
    • 如果是左括号，检查 rightBracketPopStack 栈顶是否匹配：
      • 匹配则弹出右括号栈顶
      • 不匹配则返回 false
  4. 最终检查右括号栈是否为空。

举例：对于字符串 (){}：

  • 压入栈后：{ } ( )（栈顶在右）
  • 弹出 }，压入右括号栈：[}]
  • 弹出 {，检查右括号栈顶 }，匹配，弹出右括号栈
  • 弹出 )，压入右括号栈：[)]
  • 弹出 (，检查右括号栈顶 )，匹配，弹出右括号栈
  • 右括号栈为空，返回 true。

复杂度分析

  • 时间复杂度：O(n)，遍历一次字符串。
  • 空间复杂度：O(n)，两个栈的空间。

代码

// 方法二：双栈弹出括号验证
// 先把所有字符丢到一个字符栈中，循环弹出字符串判断是否是右括号，是右括号丢到右括号栈，是左括号弹出右括号栈顶元素看是否匹配
static bool IsValid2(string s)
{
    // 检查字符串长度是否为偶数，奇数长度的字符串无法满足括号闭合条件
    if (s.Length % 2 != 0) return false;

    // 用于存储字符的栈，按顺序将字符串的字符入栈
    Stack<char> bracketPushStack = new Stack<char>();

    // 将字符串的字符按顺序入栈
    for (int i = 0; i < s.Length; i++)
    {
        bracketPushStack.Push(s[i]);
    }

    // 用于存储右括号的栈
    Stack<char> rightBracketPopStack = new Stack<char>();

    // 遍历字符栈中的每个字符
    while (bracketPushStack.Count > 0)
    {
        // 弹出栈顶字符
        char nowBracket = bracketPushStack.Pop();

        // 如果是右括号，将其入右括号栈
        if (nowBracket == ')' || nowBracket == '}' || nowBracket == ']')
        {
            rightBracketPopStack.Push(nowBracket);
        }
        // 如果是左括号，进行匹配操作
        else if (nowBracket == '(' || nowBracket == '{' || nowBracket == '[')
        {
            // 如果右括号栈为空，说明没有匹配的右括号，返回 false
            if (rightBracketPopStack.Count == 0)
            {
                return false;
            }

            // 调用 IsLeftBracketMatching 函数判断左右括号是否匹配
            bool isBracketMatching = IsLeftBracketMatching(nowBracket, rightBracketPopStack.Pop());

            // 如果不匹配，返回 false
            if (!isBracketMatching)
            {
                return false;
            }
        }
        else
        {
            // 如果字符既不是左括号也不是右括号，返回 false
            return false;
        }
    }

    // 最终检查右括号栈是否为空，若为空，则括号闭合成功，返回 true；否则，返回 false
    return rightBracketPopStack.Count == 0;
}

// 判断左右括号是否匹配
static bool IsLeftBracketMatching(char leftBracket, char rightBracket)
{
    switch (leftBracket)
    {
        case '(':
            return rightBracket == ')';
        case '{':
            return rightBracket == '}';
        case '[':
            return rightBracket == ']';
        default:
            return false; // 如果输入的不是左括号，则返回 false
    }
}

方法三：单栈弹出括号验证

思路

遍历字符串，遇到左括号就把对应的右括号压入栈，遇到右括号就弹出栈顶元素比较是否相等。这是最简洁的栈实现方式。

核心思想：遇到左括号时，预先知道它期望匹配的右括号是什么，直接把期望的右括号压入栈。

具体步骤：

  1. 遍历字符串每个字符：
    • 如果是左括号 (，压入对应的右括号 )
    • 如果是左括号 {，压入对应的右括号 }
    • 如果是左括号 [，压入对应的右括号 ]
    • 如果是右括号，检查栈顶元素是否与当前字符相等：
      • 相等则弹出栈顶（匹配成功）
      • 不相等或栈为空则返回 false
  2. 最终检查栈是否为空。

举例：对于字符串 ()[]{}：

  • 遇到 (，压入 )，栈：[)]
  • 遇到 )，弹出栈顶 )，匹配，栈：[]
  • 遇到 [，压入 ]，栈：[]]
  • 遇到 ]，弹出栈顶 ]，匹配，栈：[]
  • 遇到 {，压入 }，栈：[}]
  • 遇到 }，弹出栈顶 }，匹配，栈：[]
  • 栈为空，返回 true。

复杂度分析

  • 时间复杂度：O(n)，遍历一次字符串。
  • 空间复杂度：O(n)，栈的空间。

代码

// 方法三：单栈弹出括号验证
// 遍历字符串，如果是左括号把对应的右括号丢进栈，是右括号就弹出栈判断是否相等
static bool IsValid3(string s)
{
    // 使用栈来检查括号的有效性
    Stack<char> stack = new Stack<char>();

    // 遍历字符串的每个字符
    foreach (char c in s)
    {
        // 如果是左括号，将其对应的右括号入栈
        if (c == '(')
        {
            stack.Push(')');
        }
        else if (c == '{')
        {
            stack.Push('}');
        }
        else if (c == '[')
        {
            stack.Push(']');
        }
        else
        {
            // 如果是右括号，检查栈顶元素是否与当前右括号匹配
            // 若匹配，弹出栈顶元素；否则，返回false
            if (stack.Count == 0 || stack.Pop() != c)
            {
                return false;
            }
        }
    }

    // 如果栈为空，说明所有括号都匹配成功
    return stack.Count == 0;
}

方法四：使用字典和栈验证括号

思路

用字典存储左括号到右括号的映射。遍历字符串，遇到左括号入栈，遇到右括号检查栈顶左括号对应的右括号是否匹配。

具体步骤：

  1. 创建字典 bracketDic：( → )，{ → }，[ → ]
  2. 遍历字符串每个字符：
    • 如果是左括号（在字典键中），压入栈。
    • 如果是右括号：
      • 检查栈是否为空，为空则返回 false
      • 弹出栈顶左括号，检查其对应的右括号是否与当前字符相等
      • 不相等则返回 false
  3. 最终检查栈是否为空。

举例：对于字符串 ()[]{}：

  • 遇到 (，压入栈，栈：[(]
  • 遇到 )，栈顶 ( 对应 )，匹配，弹出，栈：[]
  • 遇到 [，压入栈，栈：[[]
  • 遇到 ]，栈顶 [ 对应 ]，匹配，弹出，栈：[]
  • 遇到 {，压入栈，栈：[{]
  • 遇到 }，栈顶 { 对应 }，匹配，弹出，栈：[]
  • 栈为空，返回 true。

复杂度分析

  • 时间复杂度：O(n)，遍历一次字符串。
  • 空间复杂度：O(n)，栈和字典的空间。

代码

// 方法四：使用字典和栈验证括号
static bool IsValid4(string s)
{
    // 创建一个字典来存储左括号及其对应的右括号
    Dictionary<char, char> bracketDic = new Dictionary<char, char>
    {
        { '(', ')' }, // 圆括号匹配
        { '{', '}' }, // 花括号匹配
        { '[', ']' } // 方括号匹配
    };

    // 创建一个栈用于存储未匹配的左括号
    Stack<char> bracketStack = new Stack<char>();

    // 遍历字符串中的每个字符
    foreach (var charVal in s)
    {
        // 如果字符是左括号，则将其入栈
        if (bracketDic.ContainsKey(charVal))
        {
            bracketStack.Push(charVal);
        }
        else
        {
            // 如果字符是右括号，检查栈是否为空并且栈顶的左括号是否与当前右括号匹配
            if (bracketStack.Count > 0 && bracketDic[bracketStack.Peek()] == charVal)
            {
                // 如果匹配，将栈顶元素弹出
                bracketStack.Pop();
            }
            else
            {
                // 如果不匹配，返回 false
                return false;
            }
        }
    }

    // 如果栈为空，说明所有括号都匹配成功，返回 true；否则，返回 false
    return bracketStack.Count == 0;
}

20.3 代码

using System;

class Program
{
    static void Main()
    {
        #region 题目

        // 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
        // 有效字符串需满足：
        // 1. 左括号必须用相同类型的右括号闭合。
        // 2. 左括号必须以正确的顺序闭合。
        // 3. 每个右括号都有一个对应的相同类型的左括号。

        // 示例 1：
        // 输入：s = "()"
        // 输出：true

        // 示例 2：
        // 输入：s = "()[]{}"
        // 输出：true

        // 示例 3：
        // 输入：s = "(]"
        // 输出：false

        // 提示：
        // 1 <= s.length <= 104
        // s 仅由括号 '()[]{}' 组成

        #endregion

        #region 测试

        // 示例 1
        string str1 = "()";
        bool result1 = IsValid1(str1);
        Console.WriteLine($"示例1 方法1 输出：{result1}");
        bool result1_2 = IsValid2(str1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");
        bool result1_3 = IsValid3(str1);
        Console.WriteLine($"示例1 方法3 输出：{result1_3}");
        bool result1_4 = IsValid4(str1);
        Console.WriteLine($"示例1 方法4 输出：{result1_4}");

        // 示例 2
        string str2 = "()[]{}";
        bool result2 = IsValid1(str2);
        Console.WriteLine($"示例2 方法1 输出：{result2}");
        bool result2_2 = IsValid2(str2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");
        bool result2_3 = IsValid3(str2);
        Console.WriteLine($"示例2 方法3 输出：{result2_3}");
        bool result2_4 = IsValid4(str2);
        Console.WriteLine($"示例2 方法4 输出：{result2_4}");

        // 示例 3
        string str3 = "(]";
        bool result3 = IsValid1(str3);
        Console.WriteLine($"示例3 方法1 输出：{result3}");
        bool result3_2 = IsValid2(str3);
        Console.WriteLine($"示例3 方法2 输出：{result3_2}");
        bool result3_3 = IsValid3(str3);
        Console.WriteLine($"示例3 方法3 输出：{result3_3}");
        bool result3_4 = IsValid4(str3);
        Console.WriteLine($"示例3 方法4 输出：{result3_4}");

        #endregion
    }

    #region 答案

    // 方法一：列表装左括号对比
    // 遍历字符串，是左括号就丢到列表里，是右括号的话就判断和列表尾部括号是否匹配
    static bool IsValid1(string s)
    {
        // 检查字符串长度是否为偶数，奇数长度的字符串无法满足括号闭合条件
        if (s.Length % 2 != 0) return false;

        // 用于存储左括号的列表
        List<char> leftBracketList = new List<char>();

        // 遍历输入字符串的每个字符
        for (int i = 0; i < s.Length; i++)
        {
            // 调用 ReturnLeftBracket 函数获取与当前右括号相匹配的左括号
            char leftBracket = ReturnLeftBracket(s[i]);

            // 如果返回的左括号不为空格，说明当前字符是右括号
            if (leftBracket != ' ')
            {
                // 检查 leftBracketList 中是否有左括号与当前右括号匹配
                if (leftBracketList.Count > 0 && leftBracketList[leftBracketList.Count - 1] == leftBracket)
                {
                    // 如果匹配成功，移除 leftBracketList 中的匹配左括号
                    leftBracketList.RemoveAt(leftBracketList.Count - 1);
                }
                else
                {
                    // 如果匹配失败，说明括号闭合顺序不正确，返回 false
                    return false;
                }
            }
            else
            {
                // 如果返回的左括号为空格，说明当前字符是左括号，将其添加到 leftBracketList 中
                leftBracketList.Add(s[i]);
            }
        }

        // 最终检查 leftBracketList 是否为空，若为空，则括号闭合成功，返回 true；否则，返回 false
        return leftBracketList.Count == 0;
    }

    // 根据右括号返回相应的左括号
    static char ReturnLeftBracket(char rightBracket)
    {
        switch (rightBracket)
        {
            case ')':
                return '(';
            case '}':
                return '{';
            case ']':
                return '[';
            default:
                return ' '; // 如果输入的不是右括号，则返回空格表示不匹配
        }
    }

    // 方法二：双栈弹出括号验证
    // 先把所有字符丢到一个字符栈中，循环弹出字符串判断是否是右括号，是右括号丢到右括号栈，是左括号弹出右括号栈顶元素看是否匹配
    static bool IsValid2(string s)
    {
        // 检查字符串长度是否为偶数，奇数长度的字符串无法满足括号闭合条件
        if (s.Length % 2 != 0) return false;

        // 用于存储字符的栈，按顺序将字符串的字符入栈
        Stack<char> bracketPushStack = new Stack<char>();

        // 将字符串的字符按顺序入栈
        for (int i = 0; i < s.Length; i++)
        {
            bracketPushStack.Push(s[i]);
        }

        // 用于存储右括号的栈
        Stack<char> rightBracketPopStack = new Stack<char>();

        // 遍历字符栈中的每个字符
        while (bracketPushStack.Count > 0)
        {
            // 弹出栈顶字符
            char nowBracket = bracketPushStack.Pop();

            // 如果是右括号，将其入右括号栈
            if (nowBracket == ')' || nowBracket == '}' || nowBracket == ']')
            {
                rightBracketPopStack.Push(nowBracket);
            }
            // 如果是左括号，进行匹配操作
            else if (nowBracket == '(' || nowBracket == '{' || nowBracket == '[')
            {
                // 如果右括号栈为空，说明没有匹配的右括号，返回 false
                if (rightBracketPopStack.Count == 0)
                {
                    return false;
                }

                // 调用 IsLeftBracketMatching 函数判断左右括号是否匹配
                bool isBracketMatching = IsLeftBracketMatching(nowBracket, rightBracketPopStack.Pop());

                // 如果不匹配，返回 false
                if (!isBracketMatching)
                {
                    return false;
                }
            }
            else
            {
                // 如果字符既不是左括号也不是右括号，返回 false
                return false;
            }
        }

        // 最终检查右括号栈是否为空，若为空，则括号闭合成功，返回 true；否则，返回 false
        return rightBracketPopStack.Count == 0;
    }

    // 判断左右括号是否匹配
    static bool IsLeftBracketMatching(char leftBracket, char rightBracket)
    {
        switch (leftBracket)
        {
            case '(':
                return rightBracket == ')';
            case '{':
                return rightBracket == '}';
            case '[':
                return rightBracket == ']';
            default:
                return false; // 如果输入的不是左括号，则返回 false
        }
    }

    // 方法三：单栈弹出括号验证
    // 遍历字符串，如果是左括号把对应的右括号丢进栈，是右括号就弹出栈判断是否相等
    static bool IsValid3(string s)
    {
        // 使用栈来检查括号的有效性
        Stack<char> stack = new Stack<char>();

        // 遍历字符串的每个字符
        foreach (char c in s)
        {
            // 如果是左括号，将其对应的右括号入栈
            if (c == '(')
            {
                stack.Push(')');
            }
            else if (c == '{')
            {
                stack.Push('}');
            }
            else if (c == '[')
            {
                stack.Push(']');
            }
            else
            {
                // 如果是右括号，检查栈顶元素是否与当前右括号匹配
                // 若匹配，弹出栈顶元素；否则，返回false
                if (stack.Count == 0 || stack.Pop() != c)
                {
                    return false;
                }
            }
        }

        // 如果栈为空，说明所有括号都匹配成功
        return stack.Count == 0;
    }


    // 方法四：使用字典和栈验证括号
    static bool IsValid4(string s)
    {
        // 创建一个字典来存储左括号及其对应的右括号
        Dictionary<char, char> bracketDic = new Dictionary<char, char>
        {
            { '(', ')' }, // 圆括号匹配
            { '{', '}' }, // 花括号匹配
            { '[', ']' } // 方括号匹配
        };

        // 创建一个栈用于存储未匹配的左括号
        Stack<char> bracketStack = new Stack<char>();

        // 遍历字符串中的每个字符
        foreach (var charVal in s)
        {
            // 如果字符是左括号，则将其入栈
            if (bracketDic.ContainsKey(charVal))
            {
                bracketStack.Push(charVal);
            }
            else
            {
                // 如果字符是右括号，检查栈是否为空并且栈顶的左括号是否与当前右括号匹配
                if (bracketStack.Count > 0 && bracketDic[bracketStack.Peek()] == charVal)
                {
                    // 如果匹配，将栈顶元素弹出
                    bracketStack.Pop();
                }
                else
                {
                    // 如果不匹配，返回 false
                    return false;
                }
            }
        }

        // 如果栈为空，说明所有括号都匹配成功，返回 true；否则，返回 false
        return bracketStack.Count == 0;
    }

    #endregion
}

20.4 运行结果

示例1 方法1 输出：True
示例1 方法2 输出：True
示例1 方法3 输出：True
示例1 方法4 输出：True
示例2 方法1 输出：True
示例2 方法2 输出：True
示例2 方法3 输出：True
示例2 方法4 输出：True
示例3 方法1 输出：False
示例3 方法2 输出：False
示例3 方法3 输出：False
示例3 方法4 输出：False
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏