678. Valid Parenthesis String

678. Valid Parenthesis String

Given a string containing only three types of characters: ‘(‘, ‘)’ and ‘*’, write a function to check whether this string is valid. We define the validity of a string by these rules:

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. An empty string is also valid. Example 1:

Input: "()"Output: True

Example 2:

Input: "(*)"Output: True

Example 3:

Input: "(*))"Output: True

Note: The string size will be in the range [1, 100].

思路： Intuition

When checking whether the string is valid, we only cared about the “balance”: the number of extra, open left brackets as we parsed through the string. For example, when checking whether ‘(()())’ is valid, we had a balance of 1, 2, 1, 2, 1, 0 as we parse through the string: ‘(’ has 1 left bracket, ‘((’ has 2, ‘(()’ has 1, and so on. This means that after parsing the first i symbols, (which may include asterisks,) we only need to keep track of what the balance could be.

For example, if we have string ‘()’, then as we parse each symbol, the set of possible values for the balance is [1] for ‘(‘; [0, 1, 2] for ‘(‘; [0, 1, 2, 3] for ‘(‘; [0, 1, 2, 3, 4] for ‘(‘, and [0, 1, 2, 3] for ‘()’.

Furthermore, we can prove these states always form a contiguous interval. Thus, we only need to know the left and right bounds of this interval. That is, we would keep those intermediate states described above as [lo, hi] = [1, 1], [0, 2], [0, 3], [0, 4], [0, 3].

Algorithm

Let lo, hi respectively be the smallest and largest possible number of open left brackets after processing the current character in the string.

If we encounter a left bracket (c == ‘(‘), then lo++, otherwise we could write a right bracket, so lo–. If we encounter what can be a left bracket (c != ‘)’), then hi++, otherwise we must write a right bracket, so hi–. If hi < 0, then the current prefix can’t be made valid no matter what our choices are. Also, we can never have less than 0 open left brackets. At the end, we should check that we can have exactly 0 open left brackets.

class Solution { public boolean checkValidString(String s) { int lo = 0, hi = 0; for (char c: s.toCharArray()) { lo += c == '(' ? 1 : -1; hi += c != ')' ? 1 : -1; if (hi < 0) break; lo = Math.max(lo, 0); } return lo == 0; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。