LeetCode

2013.12.7 00:03

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

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Solution:

　　Matching parentheses can be well handled with a stack. Left brackets are pushed into the stack, while right brackets are popped together with the matching left brackets on the stack top. If a matching is impossible, the sequence is invalid.

　　Time complexity is O(n), space complexity is O(n), where $n is the length of the sequence.

Accepted code:

 1 // 1WA, 1AC
 2 class Solution {
 3 public:
 4     bool isValid(string s) {
 5         // IMPORTANT: Please reset any member data you declared, as
 6         // the same Solution instance will be reused for each test case.
 7         if(s == ""){
 8             return true;
 9         }
10         
11         stack = new char[s.length()];
12         if(stack == nullptr){
13             return false;
14         }
15         
16         bool ret;
17         int i, len;
18         
19         pc = 0;
20         len = s.length();
21         ret = true;
22         for(i = 0; i < len; ++i){
23             switch(s[i]){
24                 case '(':
25                 case '[':
26                 case '{':
27                     stack[pc++] = s[i];
28                     break;
29                 case ')':
30                     if(pc <= 0 || stack[pc - 1] != '('){
31                         ret = false;
32                     }else{
33                         --pc;
34                     }
35                     break;
36                 case ']':
37                     if(pc <= 0 || stack[pc - 1] != '['){
38                         ret = false;
39                     }else{
40                         --pc;
41                     }
42                     break;
43                 case '}':
44                     if(pc <= 0 || stack[pc - 1] != '{'){
45                         ret = false;
46                     }else{
47                         --pc;
48                     }
49                     break;
50                 default:
51                     ret = false;
52                     break;
53             }
54             if(!ret){
55                 break;
56             }
57         }
58         // 1WA here, if stack is not empty, the sequence is invalid.
59         if(pc != 0){
60             ret = false;
61         }
62         
63         delete[] stack;
64         stack = nullptr;
65         return ret;
66     }
67 private:
68     char *stack;
69     int pc;
70 };