
问题
给定一个只包括 ‘(‘,’)’,'{‘,’}’,'[‘,’]’ 的字符串,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
输入: “()”
输出: true
输入: “()[]{}”
输出: true
输入: “(]”
输出: false
输入: “([)]”
输出: false
输入: “{[]}”
输出: true
Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
Input: “()”
Output: true
Input: “()[]{}”
Output: true
Input: “(]”
Output: false
Input: “([)]”
Output: false
Input: “{[]}”
Output: true
示例
public class Program { public static void Main(string[] args) { var s = "{[]}"; var res = IsValid(s); Console.WriteLine(res); Console.ReadKey(); } private static bool IsValid(string s) { //括号的匹配问题基本都是使用栈来解决的 //如果是奇数,肯定不匹配 if(s.Length % 2 != 0) return false; //用一个字典增加代码的可读性和可扩展性 var dic = new Dictionary<char, char>() { {')' , '('}, {']' , '['}, {'}' , '{'} }; //用栈,遇到左括号压入栈,遇到右括号删除栈顶与之匹配的左括号 var stack = new Stack<char>(); foreach(var c in s) { //发现是一个右括号 if(dic.ContainsKey(c)) { //若栈不为空,并且栈顶括号相匹配 if(stack.Count != 0 && stack.Peek() == dic[c]) { //弹出栈顶元素 stack.Pop(); } else { //若不匹配,立刻返回false return false; } } else { //发现是一个左括号,压入栈 stack.Push(c); } } //栈空表示完全匹配 return stack.Count == 0; } }
以上给出1种算法实现,以下是这个案例的输出结果:
True
分析:
显而易见,以上算法的时间复杂度为: 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/4018。