Valid Parentheses | DSA Journal

Question

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

A string is valid if:

Open brackets are closed by the same type of brackets.
Open brackets are closed in the correct order.

Example

Input: "()[]{}"

Output: true

Input: "({[]})"

Output: true

Input: "(]"

Output: false

Explanation: Incorrect closing order.

My Notes

Use a stack to store opening brackets.
Pop the stack when a closing bracket is found.
Check if popped bracket matches the closing one.
At the end, the stack should be empty.
Time complexity: O(n), Space complexity: O(n)

package main

import (
    "fmt"
)

func main() {
    result := isValid("({[]})")
    fmt.Println(result)
}

type Stack struct {
    items []string
}

func (s *Stack) Push(r string) {
    s.items = append(s.items, r)
}

func (s *Stack) Pop() (string, bool) {
    if s.IsEmpty() {
        return "", false
    }
    popped := s.items[len(s.items)-1]
    s.items = s.items[:len(s.items)-1]
    return popped, true
}

func (s *Stack) IsEmpty() bool {
    if len(s.items) == 0 {
        return true
    }
    return false
}

func isValid(s string) bool {
    stack := Stack{}

    for _, ch := range s {

        str := string(ch)

        if str == "(" || str == "[" || str == "{" {
            stack.Push(str)
        }

        if str == ")" || str == "]" || str == "}" {
            if popped, ok := stack.Pop(); ok {

                if str == ")" && popped != "(" ||
                    str == "]" && popped != "[" ||
                    str == "}" && popped != "{" {
                    return false
                }

            } else {
                return false
            }
        }

    }

    if stack.IsEmpty() {
        return true
    }

    return false
}