Consise Java solution, O(N) time, O(1) space, with reasoning and drawings


  • 0
    T

    Here is the final solution:

    class Solution {
        public boolean checkValidString(String s) {
            int lo = 0, hi = 0;
            for (int i = 0; i < s.length(); i++) {
                hi += s.charAt(i) != ')' ? +1 : -1;
                lo += s.charAt(i) != '(' ? -1 : +1;
                if (hi < 0) { return false; }
                lo = Math.max(0, lo);
            }
            return lo <= 0 && 0 <= hi;
        }
    }
    

    My reasoning when solving the problem:

    1. I recalled a similar simpler problem: if we have only ( and ), we need to track a balance variable (+1 when '(', -1 when ')'), checking two conditions 1) 0 <= balance at each step 2) 0 == balance at the end.
    2. I noticed, that '*' in that model 'modifies' the balance by -1, 0, +1. So we may replace a scalar balance with a range and check if there is a value in the range that satisfies to the above two checks. To help reasoning I drew an example:
    (*))
    ^
    |  /\
    |_/\ \____
        \
         \
    
    1. Noticed a possible problem here: with this approach the same '*' can be interpreted differently ('(', ')', '') during different checks. To be shure I draw an example:
    *)((
    ^
    |
    |    /
    |_/\/ ____
      \  /
       \/
    

    Here for intermediate check '*' would represent '(', and for the final check: ')'.

    1. I evaluated couple of ideas and concluded that is should be sufficient to shrink the range when it goes below zero. Here is an example:
    (*)(
    ^
    |
    |  /\/
    |_/\_/
    

Log in to reply
 

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