I have not solved a LeetCode challenge in a couple weeks. Went to the site and the system suggested the Valid Parentheses using the following URL: https://leetcode.com/problems/valid-parentheses/
The idea is to determine if a sequence of parentheses in a string are properly matched. Please take a look at the actual challenge using the previous URL.
Following is a screen capture of the console on my Eclipse IDE:
()
()[]{}
(]
([)]
(){
[
DONE <== TO TERMINATE INPUT
main <<< s ==>()<== isValid: true
main <<< s ==>()[]{}<== isValid: true
main <<< s ==>(]<== isValid: false
main <<< s ==>([)]<== isValid: false
main <<< s ==>(){<== isValid: false
main <<< s ==>[<== isValid: false
My approach was to extract the characters (parentheses) into a character array. Then process one character at a time. When the character represents an opening parenthesis, push it to a stack. When the character is a closing parenthesis, pop the next character from the stack and verify that they match (e.g., ‘[‘ matches ‘]’).
A condition that may arise is that the stack might be empty when attempting to process a closing parenthesis. The other is to finish processing the string with a non-empty stack.
My solution using Java follows:
import java.util.Scanner;
import java.util.Stack;
public class Solution {
/*
* Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’,
* determine if the input string is valid.
*/
public boolean isValid(String s) {
char[] charArray = s.toCharArray();
Stack<Character> stack = new Stack<Character>();
// **** ****
for (int i = 0; i < charArray.length; i++) {
char ca = charArray[i];
switch (ca) {
case ‘(‘:
case ‘{‘:
case ‘[‘:
stack.push(ca);
break;
case ‘)’:
case ‘}’:
case ‘]’:
if (stack.isEmpty()) {
return false;
}
char cs = stack.pop();
if ((ca == ‘)’) && (cs != ‘(‘)) {
return false;
}
if ((ca == ‘}’) && (cs != ‘{‘)) {
return false;
}
if ((ca == ‘]’) && (cs != ‘[‘)) {
return false;
}
break;
}
}
// **** ****
return stack.isEmpty() ? true : false;
}
/*
* test code
*/
public static void main(String[] args) {
boolean done = false;
Scanner sc = new Scanner(System.in);
Solution solution = new Solution();
while (!done) {
String s = sc.nextLine();
if (s.equals(“DONE”)) {
done = true;
continue;
}
System.out.println(“main <<< s ==>” + s + “<== isValid: ” + solution.isValid(s));
}
sc.close();
}
}
If you have comments or questions regarding this blog entry or any other post in this blog, please do not hesitate and send me an email message. I will not disclose your name unless you explicitly allow me.
John
John.canessa@gmail.com
Follow me on Twitter: @john_canessa