题目

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

有效字符串需满足：

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

示例：{()}，()[]，都是有效匹配，{()]为无效匹配

方法：栈

思路

由题目可以知道，要有效匹配，就得左括号和右括号匹配，后出现的左括号总是和先出现的右括号匹配，遵循后进先出的特点，而这一特点就和栈的特点类似

思路图

代码实现

import java.util.*;

public class test{
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isVaild("{[]}"));
    }
}

class Solution{
    //算法主体
    public boolean isVaild(String s){
        int n = s.length();
        if(n % 2 == 1){                 //字符串个数如果为奇数，直接输出false
            return false;
        }

        Map<Character,Character> brackets = new HashMap<Character, Character>(){
            {
                //建立一个哈希表，以右括号为键，左括号为值，组成键值对
                put(')' , '(');
                put(']' , '[');
                put('}' , '{');
            }
        };

        //把Deque作为栈来使用，Deque只是一个接口，是Qeque接口的增强，可以实现的类有ArrayDeque和Linkedlist
        Deque<Character> stack = new LinkedList<Character>();
        //遍历所有的字符串
        for(int i = 0; i < n; i++){
            char ch = s.charAt(i);              //charAt()方法返回指定索引处的char值
            if(brackets.containsKey(ch)){       //判断是否是右括号
                if(stack.isEmpty() || stack.peek() != brackets.get(ch)){
                    return false;
                }
                stack.pop();        //如果是右括号，且栈不为空，就让栈顶元素跟键所映射的值比较，符合就弹出当前栈顶元素
            }else {
                stack.push(ch);     //是左括号就入栈
            }
        }
        return stack.isEmpty();     //若括号全部匹配，则最后栈空，不为空说明有多的左括号
    }
}

算法主体

Java(1)

class Solution{
    //算法主体
    public boolean isVaild(String s){
        int n = s.length();
        if(n % 2 == 1){                 //字符串个数如果为奇数，直接输出false
            return false;
        }

        Map<Character,Character> brackets = new HashMap<Character, Character>(){
            {
                //建立一个哈希表，以右括号为键，左括号为值，组成键值对
                put(')' , '(');
                put(']' , '[');
                put('}' , '{');
            }
        };

        //把Deque作为栈来使用，Deque只是一个接口，是Qeque接口的增强，可以实现的类有ArrayDeque和Linkedlist
        Deque<Character> stack = new LinkedList<Character>();
        //遍历所有的字符串
        for(int i = 0; i < n; i++){
            char ch = s.charAt(i);              //charAt()方法返回指定索引处的char值
            if(brackets.containsKey(ch)){       //判断是否是右括号
                if(stack.isEmpty() || stack.peek() != brackets.get(ch)){
                    return false;
                }
                stack.pop();        //如果是右括号，且栈不为空，就让栈顶元素跟键所映射的值比较，符合就弹出当前栈顶元素
            }else {
                stack.push(ch);     //是左括号就入栈
            }
        }
        return stack.isEmpty();     //若括号全部匹配，则最后栈空，不为空说明有多的左括号
    }
}

note：建立Hashmap，用Deque接口实现Linkedlist类作为栈，charAt()方法返回索引处的 char 值，会另开文章总结

Java(2)

针对此题还有一种快速的方法，利用 foreach 迭代来遍历字符串数组

class Solution {
    //算法主体
    public boolean isVaild(String s) {
        Stack<Character> stack = new Stack<Character>();
        //使用foreach循环
        for (char c : s.toCharArray()) {        //toCharArray()方法返回一个char数组
            if (c == '(')
                stack.push(')');
            else if (c == '{')
                stack.push('}');
            else if (c == '[')
                stack.push(']');
            else if (stack.isEmpty() || stack.pop() != c)      //这里可以偷一个懒，直接弹出栈顶元素并比较，这样省去了用peek这一步骤
                return false;
        }
        return stack.isEmpty();
    }
}

C

char pairs(char a) {
    if (a == '}') return '{';
    if (a == ']') return '[';
    if (a == ')') return '(';
    return 0;
}

bool isValid(char* s) {
    int n = strlen(s);
    if (n % 2 == 1) {
        return false;
    }
    int stk[n + 1], top = 0;
    for (int i = 0; i < n; i++) {
        char ch = pairs(s[i]);
        if (ch) {				//s[i]为右括号，ch得到pairs返回的左括号，和栈顶元素比较
            if (top == 0 || stk[top - 1] != ch) {
                return false;
            }
            top--;
        } else {				//s[i]为左括号，入栈后top指针加1
            stk[top++] = s[i];
        }
    }
    return top == 0;
}