This content originally appeared on DEV Community and was authored by Yongchang He
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
There are no updates yet.
Click the Upload button above to add an update.
APA
MLA
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/
" » Judging Valid Parentheses." Yongchang He | Sciencx - Wednesday February 9, 2022, https://www.scien.cx/2022/02/09/judging-valid-parentheses/
HARVARDYongchang He | Sciencx Wednesday February 9, 2022 » Judging Valid Parentheses., viewed ,<https://www.scien.cx/2022/02/09/judging-valid-parentheses/>
VANCOUVERYongchang 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.