javastack

Leetcode Proble - 20. Valid Parentheses


I am trying to solve this leetcode problem: Given a string 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. Note that an empty string is also considered valid.

I think I am almost correct and have been working on this problem for a long time but couldn't get the correct output especially a case where input is "())".

class Solution {

public boolean isValid(String s) {

    Stack<Character> c = new Stack<>();
    int n = s.length();
    boolean bool = false;

    if (s.isEmpty() | s == null) {   // Correct
        return true;
    } 

    for (int i=0 ; i<n ; i++) {
        if (s.charAt(i) == '{') {
            c.push('{');
        } else if (s.charAt(i) == '[') {
            c.push('[');
        } else if (s.charAt(i) == '(') {
            c.push('(');

        } else if (s.charAt(i) == '}' & c.peek() == '{') {
            c.pop();
        } else if (s.charAt(i) == ']' & c.peek() == '[') {
            c.pop();
        } else if (s.charAt(i) == ')' & c.peek() == '(') {
            c.pop();
        } else {
            break;
        }
    }  
    if (c.isEmpty()) {
        return true;
    } else {
        return false;
    }
}

}


Solution

  • I think you should check stack's size before process these conditions.

    else if (s.charAt(i) == '}' & c.peek() == '{') {
            c.pop();
        } else if (s.charAt(i) == ']' & c.peek() == '[') {
            c.pop();
        } else if (s.charAt(i) == ')' & c.peek() == '(') {
            c.pop();
        }