Update valid-parenthesis-string.py

kamyu104 · web-flow · commit 4d404d08e2e1 · 2017-09-18T20:49:35.000+08:00
diff --git a/Python/valid-parenthesis-string.py b/Python/valid-parenthesis-string.py
@@ -1,6 +1,26 @@
 # Time:  O(n)
 # Space: O(1)
 
+# 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].
+
 class Solution(object):
     def checkValidString(self, s):
         """
