LC-0678 Medium LeetCode

678. Valid Parenthesis String

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 39% Topics: String, Dynamic Programming, Stack, Greedy

Reading material

Strings 12 min 1-D Dynamic Programming 16 min Stacks & Queues 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

class Solution(object):
    def checkValidString(self, s):
        """
        :type s: str
        :rtype: bool
        """
        lower, upper = 0, 0  # keep lower bound and upper bound of '(' counts
        for c in s:
            lower += 1 if c == '(' else -1
            upper -= 1 if c == ')' else -1
            if upper < 0: break
            lower = max(lower, 0)
        return lower == 0  # range of '(' count is valid

Solution from kamyu104/LeetCode-Solutions · MIT