> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/01-20-2022-20.md).

# 01/20/2022 20

Use Hashmap and stack. If we encounter an opening bracket, we simply push it onto the stack. This means we will process it later, let us simply move onto the **sub-expression** ahead. If we encounter a closing bracket, then we check the element on top of the stack. If the element at the top of the stack is an opening bracket `of the same type`, then we pop it off the stack and continue processing. Else, this implies an invalid expression. In the end, if we are left with a stack still having elements, then this implies an invalid expression.

Time O(n)

Space O(n)

```
// Some code
class Solution {
    public boolean isValid(String s) {
        if (s.length() % 2 == 1) return false;
        HashMap<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put('}', '{');
        map.put(']', '[');
        
        Stack<Character> stack = new Stack<>();
        char[] array = s.toCharArray();
        
        for (int i = 0; i < array.length; i++){
            if (map.containsKey(array[i])){
                if (stack.isEmpty() || stack.pop() != map.get(array[i]))
                    return false;
            } else {
               stack.push(array[i]); 
            }     
        }
        
        return stack.isEmpty();
    }
}
```

```
class Solution {
// Hash table that takes care of the mappings. private HashMap<Character, Character> mappings;
// Initialize hash map with mappings. This simply makes the code easier to read. 
public Solution() { 
  this.mappings = new HashMap<Character, Character>(); 
  this.mappings.put(')', '('); 
  this.mappings.put('}', '{'); 
  this.mappings.put(']', '['); 
}


public boolean isValid(String s) {


// Initialize a stack to be used in the algorithm.
Stack<Character> stack = new Stack<Character>();

for (int i = 0; i < s.length(); i++) {
  char c = s.charAt(i);

  // If the current character is a closing bracket.
  if (this.mappings.containsKey(c)) {

    // Get the top element of the stack. If the stack is empty, set a dummy value of '#'
    char topElement = stack.empty() ? '#' : stack.pop();

    // If the mapping for this bracket doesn't match the stack's top element, return false.
    if (topElement != this.mappings.get(c)) {
      return false;
    }
  } else {
    // If it was an opening bracket, push to the stack.
    stack.push(c);
  }
}

// If the stack still contains elements, then it is an invalid expression.
return stack.isEmpty();
```

} }

The basic idea is to push the right parentheses `')', ']', or '}'` into the stack each time when we encounter left ones. And if a right bracket appears in the string, we need check if the stack is empty and also whether the top element is the same with that right bracket. If not, the string is not a valid one. At last, we also need check if the stack is empty.

Time O(n)

Space O(n)

class Solution {

public boolean isValid(String s) { if(s.length() %2 == 1) return false;

```
  Stack<Character> stack = new Stack<>();
  for(int i = 0; i < s.length(); i++){
      char c = s.charAt(i);
      if(c == '('){
          stack.push(')');
      }else if(c == '{'){
          stack.push('}');
      }else if(c == '['){
          stack.push(']');
      }else if(stack.isEmpty() || c != stack.pop()){
          return false;
      }
              
  }
  return stack.isEmpty();
```

} }