notes/OJ notes/pages/Leetcode Valid-Parentheses.md

Leetcode Valid-Parentheses

2022-06-16 14:50

Data structures:

#DS #stack

Difficulty:

#coding_problem #difficulty_easy

Additional tags:

#leetcode

Revisions:

1st revision: 2022-07-03 optimize code

Related topics:

Links:

• Link to problem

---

Problem

Given a string s 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.

Examples

Example 1:

**Input:** s = "()"
**Output:** true

Example 2:

**Input:** s = "()[]{}"
**Output:** true

Example 3:

**Input:** s = "(]"
**Output:** false

Constraints

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

Thoughts

Basic stack usage. Can be implemented using std_stack or stc_vector. obviously i should use std_stack.

Solution

1st revision: optimized code

class Solution {
public:
  bool isValid(string s) {
    stack<char> st;

    char pairs[3][2] = {'(', ')', '{', '}', '[', ']'};
    const int pairSize = 3;

    for (char c : s) {
      for (int i = 0; i < pairSize; i++) {
        if (pairs[i][0] == c) {
          // {([
          st.push(c);
        } else if (pairs[i][1] == c) {
          // ]})
          if (st.empty()) {
            // empty
            return false;
          } else if (st.top() != pairs[i][0]) {
            // mismatch
            return false;
          } else {
            st.pop();
          }
        }
      }
    }

    return st.empty();
  }
};

class Solution {
public:
  bool isValid(string s) {
    vector<char> stack;
    vector<vector<char>> pairs = {{'(', ')'}, {'{', '}'}, {'[', ']'}};

    int loc;
    const int size = pairs.size();
    for (char c : s) {

      for (loc = 0; loc < size; loc++) {
        if (c == pairs[loc][1]) {
          if (stack.empty()) {
            // if there is no {([ before
            printf("No {([ before.\n");
            return false;
          } else if (stack.back() == pairs[loc][0]) {
            stack.pop_back();
          } else {
            // parens mismatch
            printf("parens mismatch: %c %c\n", stack.back(), pairs[loc][0]);
            return false;
          }
        } else if (c == pairs[loc][0]) {
          stack.push_back(c);
        }
      }
    }

    if (stack.empty()) {
      return true;
    } else {
      return false;
    }
  }
};