Blind 75
Valid Parentheses
- Problem
- LC 20
- Category
- String
- File
- blind75_LC20ValidParentheses.java
- Path
- pkg5leetcode/blind75/blind75_LC20ValidParentheses.java
- Package
- pkg5leetcode.blind75
- Command
- java pkg5leetcode/blind75/blind75_LC20ValidParentheses.java
- Approach
- Stack matches closing bracket to top opening.
- Complexity
- Time O(n), Space O(n)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.blind75;2 3/*4 * Valid Parentheses | LC 205 * APPROACH: Stack matches closing bracket to top opening.6 * COMPLEXITY: Time O(n), Space O(n)7 */8import java.util.*;9 10public class blind75_LC20ValidParentheses {11 static boolean isValid(String s) {12 Deque<Character> st = new ArrayDeque<>();13 for (char c : s.toCharArray()) {14 if (c == '(' || c == '{' || c == '[') st.push(c);15 else {16 if (st.isEmpty()) return false;17 char o = st.pop();18 if (c == ')' && o != '(' || c == '}' && o != '{' || c == ']' && o != '[') return false;19 }20 }21 return st.isEmpty();22 }23 24 public static void main(String[] args) {25 check(isValid("()[]{}"), "case1");26 check(!isValid("(]"), "case2");27 System.out.println("all tests passed");28 }29 30 static void check(boolean cond, String name) {31 if (!cond) throw new AssertionError("FAILED: " + name);32 System.out.println(" PASS " + name);33 }34}