有效的括号golang实现

发布时间：2020-12-16 09:32:18 所属栏目：大数据来源：网络整理

导读：给定一个只包括 ‘(‘，‘)‘，‘{‘，‘}‘，‘[‘，‘]‘ 的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。输入: " () " 输出: true 输入: " ()

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

输入: "()"
输出: true
输入: "()[]{}"
输出: true
输入: "(]"
输出: false
输入: "([)]"
输出: false
输入: "{[]}"
输出: true

首先理解题意：

首先空字符串必定为true
其次括号成对出现
有可能在括号中间出现成对的括号

那我们就可以想象有一个容器，一直把字符串的每个字符塞进去，当成对出现的时候就去除，当容器内没有任何元素了，那就说明字符串是有效的括号组合，否则不是

    //特殊情况，空字符串返回true
    if len(s) == 0 {
        return true
    }

    //配对字典
    m := map[string]string{")": "(","]": "[","}": "{"}
    //栈
    var stack []string
    //把字符串的每个字符放进栈中，每放一个就判断与前一个是不是配对的
    for i := 0; i < len(s); i++ {
        if len(stack) == 0 {
            stack = append(stack,string(s[i]))
        } else {
            //判断是否配对
            //如果是相同的话，那就去除栈的最后一个元素
            //如果不相同的话，那就把源字符串的对应元素加进栈中
            if stack[len(stack)-1] == m[string(s[i])] {
                stack = stack[:len(stack)-1]
            } else {
                stack = append(stack,string(s[i]))
            }
        }
    }
    //判断栈中是否没有元素
    //是的话返回true
    //否则返回false
    if len(stack) == 0 {
        return true
    } else {
        return false
    }

这里有个小技巧，就是每次我们放进容器的字符，当配对成功的时候，肯定是塞进右边的符号，所以可以构造一个以右边括号为key，左边括号为值得字典

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!