LeetCode //C - 20. Valid Parentheses-Toy模板网

这篇具有很好参考价值的文章主要介绍了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:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
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:文章来源地址https://www.toymoban.com/news/detail-659709.html

Create an empty stack.
Traverse the string one character at a time.
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.

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 initially

    for (int i = 0; i < n; i++) {
        if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
            // Push the character onto the stack
            stack[++top] = s[i];
        } else {
            // Check for matching opening bracket
            if (top == -1) {
                // No opening bracket to match
                free(stack);
                return false;
            }
            char openBracket = stack[top--];  // Pop the top of the stack
            if (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;
}