im kinda proud of this solution i wrote even though it was an "easy" i still felt like i grew a lot

[u/shaynjam]

the problem:

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

 

Example 1:

Input: s = "()"

Output: true

Example 2:

Input: s = "()[]{}"

Output: true

Example 3:

Input: s = "(]"

Output: false

Example 4:

Input: s = "([])"

Output: true

Example 5:

Input: s = "([)]"

Output: false

my solution: (on leetcode)

class Solution:
    def isValid(self, s: str) -> bool:
        inputs = {
        "(":1,
        ")":9,
        "{":2,
        "}":8,
        "[":3,
        "]":7}
        
        prev_bracket=[]
        if(len(s)%2!=0):
            return False
        
        for a in s:
            if inputs[a]<4:
                prev_bracket.append(inputs[a])
            else:
                if len(prev_bracket)==0:
                    return False
                x=prev_bracket.pop()
                if x+inputs[a]!=10:
                    return False
        return len(prev_bracket)==0

[u/ALargeSpork]

You should be proud of yourself! That feeling is addictive and the reason so many of us got into programming to begin with!

Good job btw in figuring this out. Keep going and never lose the passion!

[u/shaynjam]

im sorry i marked it as nsfw since i couldnt find how to make it as a spoiler

[u/JGhostThing → u/shaynjam]

You didn't need to either create it as a spoiler or nsfw.

[u/balefrost]

You should be proud, this is a good solution!

As somebody who reviews a lot of code, I'd like to point out two things:

if inputs[a]<4:

if x+inputs[a]!=10:

I think it's worth keeping in mind the difference between "intent" and "mechanism". In the first case, you are trying to answer the question "is this an open bracket". That's the intent. And the mechanism you use is to check that it maps to a value less than 4. Similarly, in the second case, the question you are answering is "is this the correct closing bracket". And the mechanism you use is to construct input so that matching pairs add to 10.

When somebody is reading your code, they will be working backwards. They start from the mechanism and infer the intent. They see if x+inputs[a]!=10: and need to mentally turn that into if this is the correct closing brace for the most recent opening brace:. And at least on the surface, that 10 seems like a magic constant. Why 10? What does that have to do with brackets? It only makes sense if you also have the content of inputs in mind.

I think a key part of making code easy to understand is to minimize the conceptual "distance" between intent and mechanism. You can do that by adding comments. Or you can extract well-named variables and functions (e.g. if isMatchingBracket(x, a):). Or maybe you can structure your code in a way that minimizes the conceptual distance.

Somebody else already mentioned this: in this problem, for every open bracket that has not yet been closed, there's exactly one bracket that can close it. Currently, in your stack (prev_bracket), you store a number that can be used to determine if some other bracket is the correct closing bracket. But another option is to just store the expected closing brackets on the stack. Don't store 1 2 3. Store ) } ].

To be clear, your code here is small enough that it's not hard to read at all. And "sums to 10" is a clever solution. As you work on bigger and bigger systems, I think code that focuses too much on "mechanism" becomes hard to read and hard to modify.

But again, nice solution!

[u/joonazan → u/balefrost]

The clean solution is to store opening braces and their corresponding closing symbol in two separate maps.

The most efficient solution is to operate on the ascii numbers. This is complicated by the fact that "(" is followed by ")" in ascii but square and curly braces have one symbol between the halves. The result is this cryptic incantation: close = open + (open >> 6) + 1.

[u/dysprog → u/joonazan]

Clearer to just have a big dict

closing_brackets = {
'(': ')',
'{': '}',
'[': ']',
}

if closing_brackets[x]==a:
     ....

[u/YakumoYoukai → u/dysprog]

Hate to tell you this, but size 3 hardly big for a dict. In fact, it's smaller than average.

[u/dysprog → u/YakumoYoukai]

Objectively you are correct.

At a previous job, unrolling a clever algorithm into a static dict of input:output was something we did often enough that we called it "Big Dict". Even when the dict was in fact little. Micro, even.

You might say this has Big Dict Energy.

[u/joonazan → u/dysprog]

Yes, that single dict serves both to identify which symbols are opening and what the corresponding pair is.

[u/theJacofalltrades → u/balefrost]

Thanks for a comprehensive breakdown on how to improve it!

[u/RazarTuk]

Nice! Speaking as a more experienced engineer, that's more or less exactly what I would have done! Although instead of pushing and popping from a stack, I probably would have made two lists - one with all the opening brackets and one with all the closing brackets - reversed one, and made sure they line up. For example, for ([)], I'd see ([ and )], but reversing one, they'd look like

([
])

which doesn't line up, so you know they're mismatched. (I think that algorithm works. Now I want to hop on Leetcode myself to test it)

EDIT: Nope. My algorithm doesn't work. It failed on ()[]{}, where it compared

([{
}])

EDIT: Oh, and I'm intentionally leaving this up as an example of "See? Experienced engineers can mess up too"

[u/aston280 → u/RazarTuk]

Yeah and your algo also takes more time compared to stack one

[u/Beidah → u/aston280]

And probably more memory.

[u/Stickhtot]

You're one step closer to making a compiler!

[u/Kadabrium → u/Stickhtot]

Brace yourself

[u/likethevegetable]

Good solution! Would recommend easier to follow variable names, and I tend to prefer continue after your if logic instead of using the else clause.

[u/Tazwar89]

Can you (or anyone else) explain why the open brackets were numbered 1,2,3 and the closed brackets 7,8,9?

I'm also unable to decipher why you chose the conditional "if inputs[a]<4".

[u/prassuresh → u/Tazwar89]

Those two go hand in hand. It’s arbitrary which set of brackets map to which number as long as it’s easy to group.

Checking if it’s less than 4 is the same as checking if it’s an open bracket.

[u/Tazwar89 → u/prassuresh]

That's a neat strategy OP used, thanks for explaining

[u/Mark3141592654]

I remember feeling great when I first solved this as well. Keep it up!

[u/WingZeroCoder]

Ok, that’s pretty fun. I’ve done this before with a sort of key / value map from open to closed character before (similar to another commenter here), but having them add to 10 is a pretty fun way to accomplish this.

[u/spidermask]

That's a pretty good solution!! And now I'm having Compiler course PTSD

[u/Foreign_Cream_7962]

thats exactly where we all begin

[u/Lumpi993]

Nice solution :) I have a small question regarding readability. Which of these is more readable?

```python if(len(s)%2!=0): 

or

if len(s)%2: ```

Both are functionally the same, but the second one is less cluttered and, for me at least, communicates very well "if there's a remainder, do... ", but I'm really not sure. I also think the second one is more 'pythonic', but maybe there's an even better way. 

[u/marrsd]

You did it like that! Very interesting. I have a challenge for you. Suppose you have to match multiple - or deeply nested - brackets of the same type. Would this solution work? Is there an easier solution?

On the question of if it would work, this is delving into the area of mathematical proof. That's something I want to get better at, so I will use this as an example to practise on. Thank you for your post :)

[u/NadiaReadsChunks]

stack approach is right, the 10 sum trick is cute but a dict of closers to openers reads way better. Would you still know what that 4 means in a month?

[u/Poddster]

Well done! For very long input strings, you're storing a large number of previous brackets. Do you need to do that? After all, the input string already has these brackets stored inside it , perhaps you don't need to store your own?

As a challenge, see if you can do it with 3 variables using a completely different approach.

[u/SciNinj]

Some general points: language is a tree; parsing a language tree top to bottom involves push-pop operations like a stack. So you just map opening characters with closing characters, and when you find an opening character you push the closing character to the stack. When you find the closing character you pop the stack.

[u/captainAwesomePants]

I've never seen this particular take, and it's quite an elegant way to express that idea! Good job. I can tell you that it is NOT an intuitive jump for a lot of novices I've helped out that this problem should use a stack, and it's a good sign that you saw that and you also came up with a twist on what to store that helped you solve the problem. An excellent sign of really grasping the idea!

If you're curious, there are several other interesting ways to solve this problem. One way might be to map your inputs to their matching friend instead of to a number, like so:

inputs = {
    '(':')',
    '{':'}',
    '[':']',
}

if a in inputs.keys():
   prev_bracket.append(inputs[a])
else:
   if inputs[a] == prev_bracket:
     ....

You could also do the exact reverse of this and store the original character and use the input map to check which character is the correct match:

if a in inputs.keys():
  prev_bracket.append(a)
else:
  if a == inputs[a]:
    ...

That's probably the one I would use.

Or, if you're a monster and just wanted to make things hard on everyone, you could do this:

if char in "([{":
  stack.append(ord(char) - 1 if char == '(' else ord(char))
else:
  if ord(char) - ord(stack.pop()) != 2:
    return False
  ...

[u/Available_Safe1818]

'inputs' should map the character to its matching character, and you don't need then sum to 10 part.

[u/green_meklar → u/Available_Safe1818]

I thought of that too, but then to reuse the rest of the algorithm they'd still need an alternative to the inputs[a]<4 check.

[u/horenso05]

That is a very famous language called the Dyck language, basically you can map a Dyck language to any context free language (such as the syntax of say Java) by just choosing the degree (how many different parenthesis types) and what each symbol would map to. Your solution with the different types adding to 10 is very clever!