算法练习第四天——有效的括号

算法练习第四天——有效的括号

有效的括号题目

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。

2. 左括号必须以正确的顺序闭合

示例一:

输入： str = "{}"

输出： true

示例二:

输入： str = "{}()[]"

输出： true

示例三:

输入： str = "{)"

输出： false

示例四:

输入： str = "{(}]"

输出： false

示例五:

输入： str = "{([])}"

输出： true

解题思路

先对字符串进行判断如果字符串中只有括号的左边或者只有括号的右边时直接返回false,如果字符串长度不为双数直接返回false,接下来对括号进行匹配先输入的左括号要对应后输入的右括号(顺序很重要).

方法一:栈(先进后出后进先出)

用栈来记录括号。

一、如果是任一左括号，入栈。

二、否则就是任一右括号，判断：

1. 栈是空的，返回无效，结束

2. 栈非空

1.栈顶元素必定为任一左括号，若左括号与该右括号不对应，返回无效，结束。

2.栈顶元素必定为任一左括号，左括号与该右括号对应，该左括号弹出栈，继续循环。

代码以golang为例子:

func if(s string) bool {
    n := len(s)
    if n % 2 == 1 {
        return false
    }
    temp := map[byte]byte{
        ')': '(',
        ']': '[',
        '}': '{',
    }
    a := []byte{}
    for i := 0; i < n; i++ {
        if temp[s[i]] > 0 {
            if len(a) == 0 || a[len(a)-1] != temp[s[i]] {
                return false
            }
            a = a[:len(a)-1]
        } else {
            a = append(a, s[i])
        }
    }
    return len(a) == 0
}

该解法复杂度分析

时间复杂度：O(n)，其中 n 是字符串 s 的长度。

空间复杂度：O(n+∣Σ∣)，其中 Σ 表示字符集。