【算法题解】14. 有效的括号

深藏阁楼爱情的钟 2024-03-27 11:25 126阅读 0赞

#### 文章目录 ####

*   *  题目
     *  解法：使用栈的特性
     *   *  Java 代码实现
         *  Go 代码实现
         *  复杂度分析

> 这是一道 **简单** 题。  
> 来自：[leetcode][]

### 题目 ###

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

**有效字符串需满足：**

1.  左括号必须用相同类型的右括号闭合。
2.  左括号必须以正确的顺序闭合。
3.  每个右括号都有一个对应的相同类型的左括号。

**示例 1：**

输入：s = "()"
    输出：true

**示例 2：**

输入：s = "()[]{}"
    输出：true

**示例 3：**

输入：s = "(]"
    输出：false

**提示：**  
s 仅由括号 ‘()\[\]\{\}’ 组成

### 解法：使用栈的特性 ###

有效字符串可以使用 **栈的特性（先进后出，后进先出）** 来解题。

*  当遇到 **左括号**（`‘(’`，`‘[’`，`‘{’`）时入栈。
 *  当遇到 **右括号**（`‘)’`，`‘]’`，`‘}’`）时：
    
     *  若此时栈为空，直接返回`false`。因为前面没有和这个右括号匹配的左括号。
     *  若此时栈顶元素和当前右括号不是一对，直接返回`false`。
     *  若此时栈顶元素和当前右括号成对，栈顶元素出栈，然后继续遍历字符串中的下一个元素。
 *  当将整个字符串遍历完成后：
    
     *  如果此时栈为空，返回`true`。
     *  如果此时栈不空，返回`false`。此时栈中的前括号没有对应的后括号与之成对。

以有效的括号 ‘`([]{})`’为例动图展示：  
![算法题解 - 有效的括号][-]

#### Java 代码实现 ####

使用 `HashMap` 存放成对的 **前后括号**，使用时可以直接根据 **后括号** 获取到与之对应的 **前括号**。

class Solution {
        
        public boolean isValid(String s) {
        
    
            if(s.length() % 2 != 0){
        
                return false;
            }
    
            Map<Character, Character> pairs = new HashMap<>();
            pairs.put(')', '(');
            pairs.put(']', '[');
            pairs.put('}', '{');
    
            Deque<Character> stack = new LinkedList<>();
    
            for(char c : s.toCharArray()){
        
                if(pairs.containsKey(c)){
        
                    if(stack.isEmpty() || stack.peek() != pairs.get(c)){
        
                        return false;
                    }
                    stack.pop();
                }else{
        
                    stack.push(c);
                }
            }
    
            return stack.isEmpty();
    
        }
    }

#### Go 代码实现 ####

因为Go语言本身没有实现栈这个数据结构，所以我们用切片代替，思路是一样的。

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

#### 复杂度分析 ####

**时间复杂度**： O ( N ) O(N) O(N)，N 为字符串长度。  
**空间复杂度**： O ( N ) O(N) O(N)，N 为字符串长度。`paris` 空间复杂度为常数，`stack` 空间复杂度为 N。

[leetcode]: https://leetcode.cn/problems/valid-parentheses/solutions/
[-]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/a7c8cd676cb548e7a749f962db2030f9.png