20.有效的括号
20.1 题目
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例：
示例 1：
- 输入：
s = "()" - 输出：
true
- 输入：
示例 2：
- 输入：
s = "()[]{}" - 输出：
true
- 输入：
示例 3：
- 输入：
s = "(]" - 输出：
false
- 输入：
提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
20.2 题解
列表装左括号对比
// 方法一：列表装左括号对比
// 遍历字符串，是左括号就丢到列表里，是右括号的话就判断和列表尾部括号是否匹配
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;
}
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
