AC JAVA solution using recursion


  • 2
    J

    Key idea is to keep tracking the number of "(" and ")", if, at any time, the number of right parenthesis is greater than the number of left parenthesis, return false.
    When "*" is find, treat it as "(" or ")" or empty string. When the String s is traversed, simply check if number of left parenthesis is equal to the number or right parenthesis or not.

    class Solution {
        public boolean checkValidString(String s) {
            if (s == null || s.length() == 0) return true;
            return helper(s, 0, 0, 0);
        }
        private boolean helper(String s, int left, int right, int pos) {
            if (right > left) return false;
            for (int i = pos; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    left++;
                }
                else if (s.charAt(i) == ')') {
                    right++;
                    if (right > left) return false;
                }
                else {
                    if (helper(s, left + 1, right, i + 1)) return true;
                    else if (helper(s, left, right + 1, i + 1)) return true;
                    else if (helper(s, left, right, i + 1)) return true;
                    else return false;
                }
            }
            return left == right;
        }
    }
    

  • 0

    @jun1013
    this one is good.
    Some question if anyone can help with me:
    in your last ''else" i noticed that you return false if none of the above three situation is true. Is it necessary? It will return false when your loop ends right?
    Thanks.


  • 0
    A

    Re: AC JAVA solution using recursion
    @Candle309 you don't need to go all the way to the end of the loop to decide, if s[i] == '*' is not valid, then you can skip the rest of the loop


  • 0
    C

    @Aimar88
    yeah, you right.
    Thank you.


  • 0
    A

    This solution exceeds time limit in python.


  • 0
    G

    A similar solution in C++ gets TLE. I think the intent of this question is to avoid the combinatorial search (e.g. by checking all the options for '*').


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.