LC-2116 Medium LeetCode

2116. Check if a Parentheses String Can Be Valid

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 45% Topics: String, Stack, Greedy

Reading material

Strings 12 min Stacks & Queues 11 min Greedy 11 min

Reference solution (spoiler · python)

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

class Solution(object):
    def canBeValid(self, s, locked):
        """
        :type s: str
        :type locked: str
        :rtype: bool
        """
        if len(s)%2:
            return False
        for direction, c in ((lambda x:x, '('), (reversed, ')')):
            cnt = bal = 0
            for i in direction(xrange(len(s))):
                if locked[i] == '0':
                    cnt += 1
                else:
                    bal += 1 if s[i] == c else -1
                    if cnt+bal < 0:
                        return False
        return True

Solution from kamyu104/LeetCode-Solutions · MIT