欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

LeetCode - 20. Valid Parentheses(0ms)

程序员文章站 2022-10-05 07:54:43
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: No ......

Given a string containing just the characters '('')''{''}''[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

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

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true
 1 class Solution {
 2 public:
 3     bool isValid(string s) {
 4         int l = s.length();
 5         if(l == 0) {
 6             return true;
 7         }
 8         
 9         stack<char> st;
10         for(int i=0; i<l; i++) {
11             if(s[i] == '(' || s[i] == '[' || s[i] == '{') {
12                 st.push(s[i]);
13             }
14             else if(st.size() == 0) {
15                 return false;
16             }
17             else {
18                 if(s[i] == ')') {
19                     if(st.top() == '(') {
20                         st.pop();
21                     }
22                     else {
23                         return false;
24                     }
25                 }
26                 else if(s[i] == ']') {
27                     if(st.top() == '[') {
28                         st.pop();
29                     }
30                     else {
31                         return false;
32                     }
33                 }
34                 else {
35                     if(st.top() == '{') {
36                         st.pop();
37                     }
38                     else {
39                         return false;
40                     }
41                 }
42             }
43         }
44         if(st.size() == 0) {
45             return true;
46         }
47         else {
48             return false;
49         }
50     }
51 };