Judging Valid Parentheses

Leetcode problem 20: Valid Parentheses

Question:

Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

An input string is valid if: Open brac…


This content originally appeared on DEV Community and was authored by Yongchang He

Image description

Leetcode problem 20: Valid Parentheses

Question:

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.

Below is one of the solutions:

class Solution {

    // Initialize HashMap
    static final HashMap<Character, Character> hashMap = new HashMap<>();
    static {
        hashMap.put(')', '(');
        hashMap.put('}', '{');
        hashMap.put(']', '[');
    }

    public boolean isValid(String s) {
        // Initialize a stack to be used in the algorithm.
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            // If the current character is a closing bracket
            if(hashMap.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 != hashMap.get(c)){
                    return false;
                }
            }else{
                // If it was an opening bracket, push to the stack.
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}

Let's do the test:

First test case:

Input:

"(()){[()]}"

Output:

true

And another test case:

Input:

"](())"

Output:

false

OK! Let's keep practising.


This content originally appeared on DEV Community and was authored by Yongchang He


Print Share Comment Cite Upload Translate Updates
APA

Yongchang He | Sciencx (2022-02-09T21:57:24+00:00) Judging Valid Parentheses. Retrieved from https://www.scien.cx/2022/02/09/judging-valid-parentheses/

MLA
" » Judging Valid Parentheses." Yongchang He | Sciencx - Wednesday February 9, 2022, https://www.scien.cx/2022/02/09/judging-valid-parentheses/
HARVARD
Yongchang He | Sciencx Wednesday February 9, 2022 » Judging Valid Parentheses., viewed ,<https://www.scien.cx/2022/02/09/judging-valid-parentheses/>
VANCOUVER
Yongchang He | Sciencx - » Judging Valid Parentheses. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2022/02/09/judging-valid-parentheses/
CHICAGO
" » Judging Valid Parentheses." Yongchang He | Sciencx - Accessed . https://www.scien.cx/2022/02/09/judging-valid-parentheses/
IEEE
" » Judging Valid Parentheses." Yongchang He | Sciencx [Online]. Available: https://www.scien.cx/2022/02/09/judging-valid-parentheses/. [Accessed: ]
rf:citation
» Judging Valid Parentheses | Yongchang He | Sciencx | https://www.scien.cx/2022/02/09/judging-valid-parentheses/ |

Please log in to upload a file.




There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.