String Question 15

Home / Java Practice Question / String Question 15

String Question 15

Question 25. Write a Program to check valid parenthesis string.

                           Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.

                             The following rules define a valid string:

                             Any left parenthesis '(' must have a corresponding right parenthesis ')'.

                             Any right parenthesis ')' must have a corresponding left parenthesis '('.

                             Left parenthesis '(' must go before the corresponding right parenthesis ')'.

                             '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "".

Program

  

  public boolean checkValidString(String s) {

        int low = 0;

        int high = 0;

        for (int i = 0; i < s.length(); i++) {

            if (s.charAt(i) == '(') {

                low++;

                high++;

            } else if (s.charAt(i) == ')') {

                if (low > 0) {

                    low--;

                }

                high--;

            } else {

                if (low > 0) {

                    low--;

                }

                high++;

            }

            if (high < 0) {

                return false;

            }

        }

        return low == 0;

    }