Java solution, easy to understand, check original string, then check transposed string


  • 0
    A

    Example: first check "((()" and then check "()))". In each pass, we simply make sure all CloseParent are covered; we do not care about openParen and stars, thus making the code much easier to read and understand.

    class Solution {
    public boolean checkValidString(String s) {
        // algorithm 2017/09/18: intuitively we should check closeParen, because it cannot be 'saved' later once overflown
        //      versus, if we have a lot more openParen than closeParen, at least there is a possibility we can save it later
        assert null != s;
        return closeParenCovered(s) && closeParenCovered(transpose(s));
    }
    
    private String transpose(String s) {
        char[] output = s.toCharArray().clone();
    
        int left = 0, right = output.length - 1;
        // swap first
        while (left < right) {
            char leftChar  = output[left];
            char rightChar = output[right];
            output[left++]  = transpose(rightChar);
            output[right--] = transpose(leftChar);
        }
        if (left == right) {
            // do not ignore the middle char - as we are not simply swapping
            output[left] = transpose(output[left]);
        }
        return new String(output);
    }
    
    private char transpose(char ch) {
        if ('(' == ch) return ')';
        if (')' == ch) return '(';
        return '*';
    }
    
    private boolean closeParenCovered(String s) {
        int openParens = 0;
        int stars      = 0;
        for (char ch : s.toCharArray()) {
            if ('(' == ch) {
                openParens++;
            } else if ('*' == ch) {
                stars++;
            } else {
                // we meet a closeParen, so let us offset from openParen and star
                // first try openParen, if not enough openParen, then try stars; if not starts, then it is invalid
                // why we should try openParen first before using star? because star can be used later!!
                if (0 == openParens && 0 == stars) {
                    return false;
                } else if (0 != openParens && 0 == stars) {
                    openParens--;
                } else if (0 != openParens && 0 != stars) {
                    openParens--;
                } else {
                    // 0 == openParens && 0 != stars
                    stars--;
                }
            }
        }
        return true;
    }
    

    }


Log in to reply
 

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