Java 12 lines solution, backtracking


  • 16
    1. How to check valid parenthesis w/ only ( and )? Easy. Count each char from left to right. When we see (, count++; when we see ) count--; if count < 0, it is invalid () is more than (); At last, count should == 0.
    2. This problem added *. The easiest way is to try 3 possible ways when we see it. Return true if one of them is valid.
    class Solution {
        public boolean checkValidString(String s) {
            return check(s, 0, 0);
        }
        
        private boolean check(String s, int start, int count) {
            if (count < 0) return false;
            
            for (int i = start; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c == '(') {
                    count++;
                }
                else if (c == ')') {
                    if (count <= 0) return false;
                    count--;
                }
                else if (c == '*') {
                    return check(s, i + 1, count + 1) || check(s, i + 1, count - 1) || check(s, i + 1, count);
                }
            }
            
            return count == 0;
        }
    }
    

  • 3

    When my code start have too many if else if else, next time I will remember to just attempt all possibilites at least to get solution. Thanks!


  • 0
    B

    really simple and easy to understand!!! thank you!!!


  • 0
    S

    excellent logic but TLE on python


  • 3
    B

    @wavy This is a great observation. So, whenever we have too many if-elses, we can instead just use recursion and try out all the possibilities and return the aggregate results as applicable. Thanks for leading me to it! :)


  • 0
    S

    @shawngao This solution is O(n) time and O(n) space one. Right?


  • 0
    I

    Smart. You def realized that string size is very small so trying all possibilities is feasible.


  • 0

    @sschangi I don't think so. In worst case (string contains only *), it's like a traversal of ternary tree though we can quickly stop traversing in some ) cases. So I think the upper bond is 3^n and lower bond is 2^n, n = number of *.


  • 0
    H

    Was working on this same idea that day, time went pass like anything. couldnt solve it.. Knew it gotto be a backtracking when * comes but I was using stack instead


Log in to reply
 

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