@@ -0,0 +1,2078 @@
+package stack;%0A%0Aimport java.util.Stack;%0A%0Apublic class Q678ValidParenthesisString %7B%0A%0A    //Difficulty: medium%0A    //TAG: Facebook%0A    //TAG: stack%0A%0A    /**%0A     * 678. Valid Parenthesis String%0A     * Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:%0A     *%0A     * Any left parenthesis '(' must have a corresponding right parenthesis ')'.%0A     * Any right parenthesis ')' must have a corresponding left parenthesis '('.%0A     * Left parenthesis '(' must go before the corresponding right parenthesis ')'.%0A     * '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.%0A     * An empty string is also valid.%0A     * Example 1:%0A     * Input: %22()%22%0A     * Output: True%0A     * Example 2:%0A     * Input: %22(*)%22%0A     * Output: True%0A     * Example 3:%0A     * Input: %22(*))%22%0A     * Output: True%0A     * Note:%0A     * The string size will be in the range %5B1, 100%5D.%0A     */%0A%0A    /*%0A    Solution:%0A%0A    count star in the string,%0A    when ) over (, check if we have any stars, if so, decrease one star, if not return false%0A    other wise pop a (%0A%0A    finally need check ( stack and * stack, due to if something happen like ***((( this will not be a right case%0A%0A    Time: O(n)%0A    Space: O(n)%0A     */%0A%0A    public boolean checkValidString(String s) %7B%0A        int star = 0, count = 0;%0A        Stack%3CInteger%3E stack = new Stack%3C%3E(), starStack = new Stack%3C%3E();%0A        for (int i = 0; i %3C s.length(); i++) %7B%0A            char c = s.charAt(i);%0A            if (c == '(') stack.push(i);%0A            else if (c == '*') starStack.push(i);%0A            else %7B%0A                if (stack.isEmpty()) %7B%0A                    if (!starStack.isEmpty()) starStack.pop();%0A                    else return false;%0A                %7D else stack.pop();%0A            %7D%0A        %7D%0A        while (!stack.isEmpty() && !starStack.isEmpty()) %7B%0A            if (stack.pop() %3E starStack.pop()) return false;%0A        %7D%0A        return stack.isEmpty();%0A    %7D%0A%0A%7D%0A

678. Valid Parenthesis String