678. Valid Parenthesis String¶

LeetCode Problem View on GitHub

678. Valid Parenthesis String

Medium

Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.

The following rules define a valid string:

• Any left parenthesis '(' must have a corresponding right parenthesis ')'.
• Any right parenthesis ')' must have a corresponding left parenthesis '('.
• Left parenthesis '(' must go before the corresponding right parenthesis ')'.
• '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "".

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "(*)"
Output: true

Example 3:

Input: s = "(*))"
Output: true

Constraints:

• 1 <= s.length <= 100
• s[i] is '(', ')' or '*'.

Solution¶

class Solution {
    public boolean checkValidString(String s) {
        int n = s.length();
        Stack<Integer> st = new Stack<>();
        Stack<Integer> star = new Stack<>();
        for (int i = 0; i < n; i++) {
            char current = s.charAt(i);
            if (current == '(') st.add(i);
            else if (current == '*') star.add(i);
            else {
                if (st.size() > 0) st.pop();
                else if (st.size() == 0 && star.size() == 0) return false;
                else star.pop();
            }
        }
        while (st.size() > 0 && star.size() > 0) {
            if (st.peek() > star.peek()) return false;
            else {
                st.pop();
                star.pop();
            }
        }
        return st.size() == 0;
    }
}

Complexity Analysis¶

• Time Complexity: O(?)
• Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here