Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/678.html
678. Valid Parenthesis String (Medium)
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].
Companies:
Facebook, Amazon, Bloomberg
Related Topics:
String
Similar Questions:
Solution 1.
This solution is not performant if s
contains lots of "*"
.
// OJ: https://leetcode.com/problems/valid-parenthesis-string/
// Time: O(3^S) where S is the length of string s. In the worst case every character
// is "*", so every step has 3 choices.
// Space: O(S)
class Solution {
private:
bool dfs(string &s, int start, int leftParenCnt) {
if (start == s.size()) return !leftParenCnt;
if (s[start] == '(') {
return dfs(s, start + 1, leftParenCnt + 1);
} else if (s[start] == ')') {
if (--leftParenCnt < 0) return false;
return dfs(s, start + 1, leftParenCnt);
} else {
if (dfs(s, start + 1, leftParenCnt + 1)) return true;
if (leftParenCnt >= 1 && dfs(s, start + 1, leftParenCnt - 1)) return true;
return dfs(s, start + 1, leftParenCnt);
}
}
public:
bool checkValidString(string s) {
return dfs(s, 0, 0);
}
};
Solution 2.
Let diff
be count of left parenthesis minus count of right parenthesis.
When we meet:
(
, we incrementdiff
.)
, we decrementdiff
.*
, we have three choices which makes thediff
become a range –[diff - 1, diff + 1]
.
So we use maxDiff
/minDiff
to record the maximum/minimum diff
we can get.
When we meet:
(
,++maxDiff
and++minDiff
.)
,--maxDiff
and--minDiff
.*
,++maxDiff
and--minDiff
.
If maxDiff
become negative, it means it’s already invalid, we should return false
.
Whenever minDiff
falls below 0
, we should force it to be 0
because we never accept negative diff
during the process.
After scanning through string s
, as long as minDiff
is 0
, this string can be a valid one.
Whenever
minDiff
falls below0
, we should force it to be0
because we never accept negativediff
during the process.
minDiff
means the diff
we got if we always try to replace *
with )
. If minDiff
become -1
, it means that this replacement results in more )
than (
, so it should be avoided. To avoid it, we simply reset minDiff
from -1
to 0
which implies we only replace *
with (
or empty string.
Example: (**)
- Seeing
(
, the range becomes[1, 1]
. - Seeing
*
, the range becomes[0, 2]
.0
correponds to()
,1
to(_
,2
to((
. - Seeing
*
, the range becomes[-1,3]
. But-1
is invalid because it means())
and should be avoided. So we correct the range to[0, 3]
. - Seeing
)
, the range becomes[-1, 2]
. Again, we correct the range to[0, 2]
(because-1
means()_)
or(_))
)
The final [0, 2]
range means that we can either get a perfect string, or has 1
or 2
more (
available (which are created by *
).
// OJ: https://leetcode.com/problems/valid-parenthesis-string/
// Time: O(S)
// Space: O(1)
class Solution {
public:
bool checkValidString(string s) {
int maxDiff = 0, minDiff = 0;
for (char c : s) {
maxDiff += (c == '(' || c == '*') ? 1 : -1;
minDiff += (c == ')' || c == '*') ? -1 : 1;
if (maxDiff < 0) return false;
minDiff = max(0, minDiff);
}
return minDiff == 0;
}
};
-
class Solution { public boolean checkValidString(String s) { Stack<Integer> parenthesesStack = new Stack<Integer>(); Queue<Integer> asterisksQueue = new LinkedList<Integer>(); int length = s.length(); for (int i = 0; i < length; i++) { char c = s.charAt(i); if (c == '*') asterisksQueue.offer(i); else if (c == '(') parenthesesStack.push(i); else if (c == ')') { if (!parenthesesStack.isEmpty()) parenthesesStack.pop(); else if (!asterisksQueue.isEmpty()) asterisksQueue.poll(); else return false; } } if (parenthesesStack.isEmpty()) return true; else { Stack<Integer> newParenthesesStack = new Stack<Integer>(); while (!parenthesesStack.isEmpty()) newParenthesesStack.push(parenthesesStack.pop()); while (!newParenthesesStack.isEmpty() && !asterisksQueue.isEmpty()) { int parenthesisIndex = newParenthesesStack.peek(); int asteriskIndex = asterisksQueue.poll(); if (parenthesisIndex < asteriskIndex) newParenthesesStack.pop(); } return newParenthesesStack.isEmpty(); } } } ############ class Solution { public boolean checkValidString(String s) { int x = 0; int n = s.length(); for (int i = 0; i < n; ++i) { if (s.charAt(i) != ')') { ++x; } else if (x > 0) { --x; } else { return false; } } x = 0; for (int i = n - 1; i >= 0; --i) { if (s.charAt(i) != '(') { ++x; } else if (x > 0) { --x; } else { return false; } } return true; } }
-
// OJ: https://leetcode.com/problems/valid-parenthesis-string/ // Time: O(3^S) where S is the length of string s. In the worst case every character // is "*", so every step has 3 choices. // Space: O(S) class Solution { private: bool dfs(string &s, int start, int leftParenCnt) { if (start == s.size()) return !leftParenCnt; if (s[start] == '(') { return dfs(s, start + 1, leftParenCnt + 1); } else if (s[start] == ')') { if (--leftParenCnt < 0) return false; return dfs(s, start + 1, leftParenCnt); } else { if (dfs(s, start + 1, leftParenCnt + 1)) return true; if (leftParenCnt >= 1 && dfs(s, start + 1, leftParenCnt - 1)) return true; return dfs(s, start + 1, leftParenCnt); } } public: bool checkValidString(string s) { return dfs(s, 0, 0); } };
-
class Solution: def checkValidString(self, s: str) -> bool: x = 0 for c in s: if c in '(*': x += 1 elif x: x -= 1 else: return False x = 0 for c in s[::-1]: if c in '*)': x += 1 elif x: x -= 1 else: return False return True ############ class Solution(object): def checkValidString(self, s): """ :type s: str :rtype: bool """ old_set = set([0]) for c in s: new_set = set() if c == '(': for t in old_set: new_set.add(t + 1) elif c == ')': for t in old_set: if t > 0: new_set.add(t - 1) elif c == '*': for t in old_set: new_set.add(t + 1) new_set.add(t) if t > 0: new_set.add(t - 1) old_set = new_set return 0 in old_set
-
func checkValidString(s string) bool { x := 0 for _, c := range s { if c != ')' { x++ } else if x > 0 { x-- } else { return false } } x = 0 for i := len(s) - 1; i >= 0; i-- { if s[i] != '(' { x++ } else if x > 0 { x-- } else { return false } } return true }