diff options
Diffstat (limited to 'valid_parentheses_string.c')
-rw-r--r-- | valid_parentheses_string.c | 42 |
1 files changed, 42 insertions, 0 deletions
diff --git a/valid_parentheses_string.c b/valid_parentheses_string.c new file mode 100644 index 0000000..efd86f0 --- /dev/null +++ b/valid_parentheses_string.c @@ -0,0 +1,42 @@ +// 678. Valid Parenthesis String +#include "leetcode.h" + +/* + * given a string 's' containing only three types of characters, 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. start could be treated as a single right + * parenthesis, a single left parenthesis, or an empty string. + */ + +bool checkValidString(char *s) { + int n = strlen(s), cnt = 0; + for (int i = 0; i < n; i++) { + if (s[i] == '(' || s[i] == '*') + cnt++; + else { + cnt--; + if (cnt < 0) + return 0; + } + } + cnt = 0; + for (int i = n - 1; i >= 0; i--) { + if (s[i] == ')' || s[i] == '*') + cnt++; + else { + cnt--; + if (cnt < 0) + return 0; + } + } + return 1; +} + +int main() { + char *s1 = "()", *s2 = "(*)", *s3 = "(*))"; + printf("%d\n", checkValidString(s1)); // expect: 1 + printf("%d\n", checkValidString(s2)); // expect: 1 + printf("%d\n", checkValidString(s3)); // expect: 1 +} |