LeetCode //C - 20. Valid Parentheses

20. Valid Parentheses

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.
3. Every close bracket has a corresponding open bracket of the same type.
    

Example 1:

Input: s = “()”
Output: true

Example 2:

Input: s = “()[]{}”
Output: true

Example 3:

Input: s = “(]”
Output: false

Constraints:

• $1<=s.length<=10^4$
• s consists of parentheses only ‘()[]{}’.

From: LeetCode
Link: 20. Valid Parentheses

---

Solution:

Ideas：

To determine if the string contains valid parentheses, we can use a stack. Here’s the approach:

1. Create an empty stack.
2. Traverse the string one character at a time.
3. For each character:

• If it’s an opening bracket ((, {, or [), push it onto the stack.
• If it’s a closing bracket (), }, or ]), check if the stack is empty. If it’s empty, then there’s no matching opening bracket, so return false.
• If the stack is not empty, pop the top element and check if it matches the corresponding opening bracket for the current closing bracket. If not, return false.

4. After processing all characters in the string, check if the stack is empty. If it’s empty, then all opening brackets have been matched, so return true. Otherwise, return false.

Code:

bool isValid(char * s) {int n = strlen(s);char *stack = (char *)malloc(n * sizeof(char));int top = -1;  // stack is empty initiallyfor (int i = 0; i < n; i++) {if (s[i] == '(' || s[i] == '{' || s[i] == '[') {// Push the character onto the stackstack[++top] = s[i];} else {// Check for matching opening bracketif (top == -1) {// No opening bracket to matchfree(stack);return false;}char openBracket = stack[top--];  // Pop the top of the stackif (s[i] == ')' && openBracket != '(') {free(stack);return false;}if (s[i] == '}' && openBracket != '{') {free(stack);return false;}if (s[i] == ']' && openBracket != '[') {free(stack);return false;}}}bool result = (top == -1);free(stack);return result;
}