valid_parentheses

View Source

 1# @leet start
 2class Solution:
 3    def isValid(self, s: str) -> bool:
 4        """
 5        This function returns either true or false given a string of parentheses,
 6        braces, and brackets.
 7
 8        A string is considered balanced if each opening member is closed
 9        `[{}]` is considered balanced, because the two outermost brackets are lined up,
10        and the two innermost braces also line up.
11        `[[]` is not considered balanced, because the first bracket has no closing bracket,
12        even though the second opening bracket does.
13
14        Thus, we go through the string and do two different things.
15        1. If the character is an opening char, add it to a stack.
16        2. If the character is a closing char, check to make sure it complements the char
17        on the top of the stack. If the stack is empty or the char does not match, return false.
18        This corresponds to a case like '{]'.
19
20        To make this easier, we can create a key -> val mapping of opening to closing chars
21        and a reverse mapping, where closing chars are mapped to opening chars.
22
23        We do this so we only have to write the pairs once, i.e. '{' -> '}'.
24        If we did this in every if else case, if we have to add a new pair, it would become cumbersome quickly.
25        """
26        mapping = {'{': '}', '[': ']', '(': ')'}
27        reverse_mapping = {v: k for k, v in mapping.items()}
28        stack = []
29        for c in s:
30            if c in mapping:
31                stack.append(c)
32            if c in reverse_mapping:
33                if not stack:
34                    return False
35                top = stack.pop()
36                if top != reverse_mapping[c]:
37                    return False
38
39        return not stack
40
41
42
43# @leet end
44sol = Solution()
45
46def test_braces():
47	assert(sol.isValid("{}"))
48
49def test_parens():
50	assert(sol.isValid("()"))
51
52def test_brackets():
53	assert(sol.isValid("[]"))
54
55def false_cases():
56    assert(sol.isValid("{}["))
57    assert(sol.isValid("())"))
58    assert(sol.isValid("[]}"))
59    assert(sol.isValid("[[]"))

class Solution: View Source

 3class Solution:
 4    def isValid(self, s: str) -> bool:
 5        """
 6        This function returns either true or false given a string of parentheses,
 7        braces, and brackets.
 8
 9        A string is considered balanced if each opening member is closed
10        `[{}]` is considered balanced, because the two outermost brackets are lined up,
11        and the two innermost braces also line up.
12        `[[]` is not considered balanced, because the first bracket has no closing bracket,
13        even though the second opening bracket does.
14
15        Thus, we go through the string and do two different things.
16        1. If the character is an opening char, add it to a stack.
17        2. If the character is a closing char, check to make sure it complements the char
18        on the top of the stack. If the stack is empty or the char does not match, return false.
19        This corresponds to a case like '{]'.
20
21        To make this easier, we can create a key -> val mapping of opening to closing chars
22        and a reverse mapping, where closing chars are mapped to opening chars.
23
24        We do this so we only have to write the pairs once, i.e. '{' -> '}'.
25        If we did this in every if else case, if we have to add a new pair, it would become cumbersome quickly.
26        """
27        mapping = {'{': '}', '[': ']', '(': ')'}
28        reverse_mapping = {v: k for k, v in mapping.items()}
29        stack = []
30        for c in s:
31            if c in mapping:
32                stack.append(c)
33            if c in reverse_mapping:
34                if not stack:
35                    return False
36                top = stack.pop()
37                if top != reverse_mapping[c]:
38                    return False
39
40        return not stack

def isValid(self, s: str) -> bool: View Source

 4    def isValid(self, s: str) -> bool:
 5        """
 6        This function returns either true or false given a string of parentheses,
 7        braces, and brackets.
 8
 9        A string is considered balanced if each opening member is closed
10        `[{}]` is considered balanced, because the two outermost brackets are lined up,
11        and the two innermost braces also line up.
12        `[[]` is not considered balanced, because the first bracket has no closing bracket,
13        even though the second opening bracket does.
14
15        Thus, we go through the string and do two different things.
16        1. If the character is an opening char, add it to a stack.
17        2. If the character is a closing char, check to make sure it complements the char
18        on the top of the stack. If the stack is empty or the char does not match, return false.
19        This corresponds to a case like '{]'.
20
21        To make this easier, we can create a key -> val mapping of opening to closing chars
22        and a reverse mapping, where closing chars are mapped to opening chars.
23
24        We do this so we only have to write the pairs once, i.e. '{' -> '}'.
25        If we did this in every if else case, if we have to add a new pair, it would become cumbersome quickly.
26        """
27        mapping = {'{': '}', '[': ']', '(': ')'}
28        reverse_mapping = {v: k for k, v in mapping.items()}
29        stack = []
30        for c in s:
31            if c in mapping:
32                stack.append(c)
33            if c in reverse_mapping:
34                if not stack:
35                    return False
36                top = stack.pop()
37                if top != reverse_mapping[c]:
38                    return False
39
40        return not stack

This function returns either true or false given a string of parentheses, braces, and brackets.

A string is considered balanced if each opening member is closed [{}] is considered balanced, because the two outermost brackets are lined up, and the two innermost braces also line up. [[] is not considered balanced, because the first bracket has no closing bracket, even though the second opening bracket does.

Thus, we go through the string and do two different things.

If the character is an opening char, add it to a stack.
If the character is a closing char, check to make sure it complements the char on the top of the stack. If the stack is empty or the char does not match, return false. This corresponds to a case like '{]'.

To make this easier, we can create a key -> val mapping of opening to closing chars and a reverse mapping, where closing chars are mapped to opening chars.

We do this so we only have to write the pairs once, i.e. '{' -> '}'. If we did this in every if else case, if we have to add a new pair, it would become cumbersome quickly.

sol = <Solution object>

def test_braces(): View Source

47def test_braces():
48	assert(sol.isValid("{}"))

def test_parens(): View Source

50def test_parens():
51	assert(sol.isValid("()"))

def test_brackets(): View Source

53def test_brackets():
54	assert(sol.isValid("[]"))

def false_cases(): View Source

56def false_cases():
57    assert(sol.isValid("{}["))
58    assert(sol.isValid("())"))
59    assert(sol.isValid("[]}"))
60    assert(sol.isValid("[[]"))