Interview Classic 150 Questions P20 Valid Parentheses

---

Timeline

Timeline

2025-11-18

init

Stack

---

Problem:

P20 Valid Parentheses

https://leetcode.cn/problems/valid-parentheses/description/?envType=study-plan-v2&envId=top-interview-150

A classic stack problem. Note that at the end you need to check if the stack is empty; if it’s not empty, it’s invalid.
Code:

#include <string>
#include <stack>

using std::stack;
using std::string;

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

		for (char &ch : s) {
			if (ch == '(' || ch == '[' || ch == '{') {
				st.push(ch);
			} else if (!st.empty() && ch == ')') {
				curr = st.top();
				st.pop();
				if (curr != '(') return false;
			} else if (!st.empty() && ch == ']') {
				curr = st.top();
				st.pop();
				if (curr != '[') return false;
			} else if (!st.empty() && ch == '}') {
				curr = st.top();
				st.pop();
				if (curr != '{') return false;
			} else {
				return false;
			}
		}
		return st.empty();
	}
};

leetcode hot 100 rewrite

#include <string>
#include <stack>

using std::string;
using std::stack;

class Solution {
    public:
        bool isValid(string s)
        {
                // 1 <= s.length <= 104
                // s consists only of parentheses '()[]{}'
                stack<char> stk;
                char curr;

                for (char ch : s) {
                        if (ch == '(' || ch == '[' || ch == '{') {
                                stk.push(ch);
                        } else if (!stk.empty() && ch == ')') {
                                if (stk.top() != '(')
                                        return false;
                                stk.pop();

                        } else if (!stk.empty() && ch == ']') {
                                if (stk.top() != '[')
                                        return false;
                                stk.pop();
                        } else if (!stk.empty() && ch == '}') {
                                if (stk.top() != '{')
                                        return false;
                                stk.pop();
                        } else {
                                return false;
                        }
                }

                return stk.empty();
        }
};