LeetCode.20(合并区间)

• LeetCode.20(合并区间)

• 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

  有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

  注意空字符串可被认为是有效字符串。

• 示例1：

  输入: "()"
  输出: true
  

  示例 2:

  输入: "()[]{}"
  输出: true
  

  示例 3:

  输入: "(]"
  输出: false
  

  示例 4:

  输入: "([)]"
  输出: false
  

  示例 5:

  输入: "{[]}"
  输出: true
  

• 代码:

  //2020_04_21
  class Solution {
  public:
      bool isValid(string s)
      {
          stack<char> st;//定义栈
          for (int i = 0; i < s.size(); i++)//遍历字符串
          {
              if (s[i] == '(' || s[i] == '[' || s[i] == '{')//当前字符是左括号
              {
                  st.push(s[i]);//压栈
                  continue;
              }
              //当前字符是右括号
              else if (st.empty())//若栈空，则返回false
              {
                  return false;
              }
              else if (st.top() == '(' && s[i] == ')' ||
                      st.top() == '[' && s[i] == ']' ||
                      st.top() == '{' && s[i] == '}')
                      st.pop();//若左括号与其匹配，则出栈
              else
              {
                  return false;//若不匹配，则返回false
              }
          }
          return st.empty();//若最后栈空，则返回true
      }
  };
  

• 结果：