LeetCode 20. Valid Parentheses

Stack (Optimized)

public boolean isValid(String s) {
    if (s == null || s.length() == 0) {
        return true;
    }

    int ptr = 0;
    char[] map = new char[s.length()];

    for (char ch : s.toCharArray()) {
        switch (ch) {
            case '(':
            case '{':
            case '[':
                map[ptr++] = ch;
                break;
            case ')':
                if (ptr == 0 || map[--ptr] != '(')
                    return false;
                break;
            case '}':
                if (ptr == 0 || map[--ptr] != '{')
                    return false;
                break;
            case ']':
                if (ptr == 0 || map[--ptr] != '[')
                    return false;
                break;
        }
    }

    return ptr == 0;
}

This problem can be solved by using a stack. The solution provided by LeetCode uses the Stack class. However, it can be simulated by an array. First, we create an empty array map that has the same size as the string s. Then we iterate through each character of s and when we encounter a left parenthesis, we store the parenthesis in map at the ptr index. Also, we increment ptr by one. (similar to push in Stack). If we encounter a right parentesis, we check if the right parenthesis has a corresponding left parenthesis stored at ptr -1 in map. If not, return false. Finally, we check if the ptr equals 0 (similar to an empty Stack).

Time Complexity: O(n)

Extra Space: O(n)