Leetcode --- Valid Parentheses
===

## Description

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.

### Examples

* Ex1:
**Input**: s = "()"
**Output**: true
* Ex2:
**Input**: s = "()[]{}"
**Output**: true
* Ex3:
**Input**: s = "(]"
**Output**: false
* Ex4:
**Input**: s = "([)]"
**Output**: false
* Ex5:
**Input**: s = "{[]}"
**Output**: true

### Constraints

* 1 <= s.length <= 10^4^
* s consists of parentheses only '()[]{}'.

## Solution

The key idea is to find the first valid pair at the internal array,and I can delete the valid pair,and continue to find the second valid pair,the third valid pair,so forth.

First step:
I'll find a first pair in the internal array,and the first closing bracket is what I want to find.

Second step:
I'll determine the first parentheses pair is valid or not by check its left-hand-side parentheses,if yes,I continue to determine the second parentheses pair,if not,the string is over and fail.

Third step:
I'll do the second step things iteratively until all of elements in the array are worked out or the string is over in advance.Eventually,I can determine the answer through whether the string is empty.

### Implement code

class Solution {
    public boolean isValid(String s) {
        StringBuilder sb = new StringBuilder(s);
        int i =1,l=sb.length();
        while(l>1 && i<l )
        {
            if(i == 0)
            {
                i++;
                continue;
            }
            char tmp1 = sb.charAt(i);
            char tmp2 = sb.charAt(i-1);
            if( (tmp1 == ')' && tmp2 == '(') || (tmp1 == '}' && tmp2 == '{') || (tmp1 == ']' && tmp2 == '[') )
            {
                sb = sb.deleteCharAt(i);
                sb = sb.deleteCharAt(i-1);
                i = i-1;
                l = sb.length();
            }
            else
                i++;
        }
        if(sb.length() == 0)
            return true;
        else 
            return false;
    }
}

### Complexity Analysis

* Time Complexity
The while loop will be executed n times if there is no matching pair,it will cost O(n),which n is length of input string s.
**Total time complexity:**
==O(n)==
* Space Complexity
I created a StringBuilder whose API simplifies what I want to do on string,its size as large as input string s,therefore,it cost O(n).
**Total space complexity:**
==O(n)==

### Submissions on Leetcode

Runtime: **1 ms, faster than 98.64%** of Java online submissions for Valid Parentheses.
Memory Usage: **36.7 MB, less than 97.47%** of Java online submissions for Valid Parentheses.

###### tags: `Leetcode` `Easy` `String`