package com.fishercoder.solutions;

import java.util.Stack;

/**
 * 678. Valid Parenthesis String
 *
 *  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:

 1. Any left parenthesis '(' must have a corresponding right parenthesis ')'.
 2. Any right parenthesis ')' must have a corresponding left parenthesis '('.
 3. Left parenthesis '(' must go before the corresponding right parenthesis ')'.
 4. '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
 5. An empty string is also valid.

 Example 1:
 Input: "()"
 Output: True

 Example 2:
 Input: "(*)"
 Output: True

 Example 3:
 Input: "(*))"
 Output: True

 Note:
 The string size will be in the range [1, 100].
 */
public class _678 {
    public static class Solution1 {
        /**
         * This solution is correct, but will result in TLE by test4
         */
        public boolean checkValidString(String s) {
            if (!s.contains("*")) {
                Stack<Character> stack = new Stack();
                int i = 0;
                while (i < s.length()) {
                    if (s.charAt(i) == '(') {
                        stack.push(s.charAt(i));
                    } else {
                        if (stack.isEmpty()) {
                            return false;
                        } else {
                            stack.pop();
                        }
                    }
                    i++;
                }
                return stack.isEmpty();
            } else {
                int index = s.indexOf("*");
                String transformedS = s.substring(0, index) + s.substring(index + 1);
                if (checkValidString(transformedS)) {
                    return true;
                }
                transformedS = s.substring(0, index) + "(" + s.substring(index + 1);
                if (checkValidString(transformedS)) {
                    return true;
                }
                transformedS = s.substring(0, index) + ")" + s.substring(index + 1);
                if (checkValidString(transformedS)) {
                    return true;
                }
            }
            return false;
        }
    }

    public static class Solution2 {
        public boolean checkValidString(String s) {
            return isValid(s, 0, 0);
        }

        private boolean isValid(String s, int start, int cnt) {
            if (cnt < 0) {
                return false;
            }
            for (int i = start; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c == '(') {
                    cnt++;
                } else if (c == ')') {
                    if (cnt <= 0) {
                        return false;
                    }
                    cnt--;
                } else if (c == '*') {
                    /**Extra caution: start should be i+1, not start+1 !*/
                    return isValid(s, i + 1, cnt + 1)
                            || isValid(s, i + 1, cnt - 1)
                            || isValid(s, i + 1, cnt);
                }
            }
            return cnt == 0;
        }
    }

    public static class Solution3 {
        /**
         * Greedy solution:
         * 1. Let lo mean the lowest possible open left paren
         * 2. Let hi mean the possibilities of highest possible open left paren, so as long as s.charAt(i) != ')', it's possible to be a '(', so we'll increment hi by 1
         * 2. If at any time, hi becomes negative, that means this string will never be valid
         * 3. Each time, we'll let lo be at a minimum of zero
         */
        public boolean checkValidString(String s) {
            int lo = 0;
            int hi = 0;
            for (int i = 0; i < s.length(); i++) {
                lo += s.charAt(i) == '(' ? 1 : -1;
                hi += s.charAt(i) != ')' ? 1 : -1;
                if (hi < 0) {
                    break;
                }
                lo = Math.max(0, lo);
            }
            return lo == 0;
        }
    }
}

@@ -58,807 +58,8 @@
 k;%0A%0A
-/**%0A * 678. Valid Parenthesis String%0A *%0A *  Given a string containing only three types of characters: '(', ')' and '*',%0A *  write a function to check whether this string is valid. We define the validity of a string by these rules:%0A%0A 1. Any left parenthesis '(' must have a corresponding right parenthesis ')'.%0A 2. Any right parenthesis ')' must have a corresponding left parenthesis '('.%0A 3. Left parenthesis '(' must go before the corresponding right parenthesis ')'.%0A 4. '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.%0A 5. An empty string is also valid.%0A%0A Example 1:%0A Input: %22()%22%0A Output: True%0A%0A Example 2:%0A Input: %22(*)%22%0A Output: True%0A%0A Example 3:%0A Input: %22(*))%22%0A Output: True%0A%0A Note:%0A The string size will be in the range %5B1, 100%5D.%0A */%0A
 publ

refactor 678