aboutsummaryrefslogtreecommitdiff
path: root/valid_parentheses_string.c
diff options
context:
space:
mode:
Diffstat (limited to 'valid_parentheses_string.c')
-rw-r--r--valid_parentheses_string.c42
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
+}