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 };