Valid Parentheses

1. Problem Description

Given a string containing only the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, determine whether the string is a valid parentheses sequence. Parentheses must close in the correct order. “()” and “()[]{}” are valid, while “(]” and “([)]” are invalid.

2. Approach

1. Approach 1
   • Stack
   • Traverse all elements. Push a left parenthesis onto the stack. For a right parenthesis, take the top element and check whether it matches the right parenthesis
   • A HashMap is used to determine whether they match
   • If traversal finishes and the stack is empty, the parentheses sequence is valid
2. Approach 2
   • String replacement

3. Implementation

3.1. Stack

var m = map[rune]rune {
    '(':')',
    '[':']',
    '{':'}',
}

func isValid(s string) bool {
    stack := make([]rune, 0)
    for _, r := range []rune(s) {
        if isLeft(r) {
            stack = append(stack, r)
        } else if isRight(r){
            if len(stack) > 0 && isMatch(stack[len(stack)-1], r) {
                stack = stack[:len(stack)-1]
                continue
            }
            return false
        } else {
            return false
        }
    }

    return len(stack) == 0
}

func isLeft(r rune) bool {
    return r == '(' || r == '{' || r == '['
}

func isRight(r rune) bool {
    return r == ')' || r == '}' || r == ']'
}

func isMatch(left, right rune) bool{
    return m[left] == right
}

3.2. String Replacement

func isValid2(s string) bool {
	if len(s)%2 != 0 {
		return false
	}

	flag := true
	for flag {
		oldLength := len(s)
		s = strings.Replace(s, "()", "", -1)
		s = strings.Replace(s, "{}", "", -1)
		s = strings.Replace(s, "[]", "", -1)

		if len(s) == oldLength {
			flag = false
		}
	}

	return len(s) == 0
}

4. References

• Parentheses Sequence _ NowCoder
• Valid Parentheses (Auxiliary Stack, Minimal + Diagram) - LeetCode