题目连结: 20. Valid Parentheses; Easy

题目说明:

Given a string s 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.
Every close bracket has a corresponding open bracket of the same type.

简单来说就是判断字串中左括弧与右括弧是否都成对显示。

Example1

Input: s = "()"Output: true

Example2

Input: s = "()[]{}"Output: true

Example3

Input: s = "(]"Output: false

Example4

Input: s = "{[]}"Output: true

Example5

Input: s = "()}}"Output: false

本次解题心得:

利用Stack后进先出的特性，刚好可以使用在左右成对的比较()、{}、[]，直接排除有问题的配对，不符合题目条件的有哪些呢?

自己的解答:

public class Solution {    public bool IsValid(string s) {            if (string.IsNullOrWhiteSpace(s))                return false;            if ((s.ToCharArray().Length % 2) != 0) //不是成对的char                return false;            Stack<char> st = new Stack<char>(); //使用Stack来存放，特性:先进后出            foreach (char ch in s)            {                if (ch == '(' || ch == '{' || ch == '[')                    st.Push(ch);                if (st.Count() == 0) //刚开始与最后，如果出现连续两个右括弧，Stack.Pop()会出现exception                    return false;                if ( ch == ')' && st.Pop() != '(' )                    return false;                if (ch == '}' && st.Pop() != '{')                    return false;                if (ch == ']' && st.Pop() != '[')                    return false;            }            return st.Count() == 0; //如果Stack还有未配对的括弧，代表false    }}

参考别人优化后的解答:

public class Solution {    public bool IsValid(string s) {            Stack<char> st = new Stack<char>();            foreach (var ch in s)            {                if (ch == '(')                 {                     st.Push(')'); //右括弧(出现时，把相对应的左括弧)存进Stack                    continue; //离开迴圈，继续执行下一字元                }                if (ch == '{')                {                    st.Push('}'); //右括弧{出现时，把相对应的左括弧}存进Stack                    continue;                }                if (ch == '[')                {                    st.Push(']'); //右括弧[出现时，把相对应的左括弧]存进Stack                    continue;                }                if (st.Count == 0 || ch != st.Pop()) //左括弧出现，若没有相对应的右括弧Pop出来，则表示不成对                    return false;            }            return st.Count() == 0; //如果Stack还有未配对的括弧，表示不成对    }}

参考资料来源:
[LeetCode C#] 20. Valid Parentheses — Stack
C# Solution - elegant and simple 7 lines (Runtime: faster than 99.90%; Memory: less than 48.94%)