算法LeetCode之有效括号

小灰灰 2024-03-24 11:43 53阅读 0赞

> 这里是引用给定一个只包括 ‘(’，‘)’，‘\{’，‘\}’，‘\[’，‘\]’ 的字符串 s ，判断字符串是否有效。  
> 有效字符串需满足：  
> 左括号必须用相同类型的右括号闭合。  
> 左括号必须以正确的顺序闭合。  
> 每个右括号都有一个对应的相同类型的左括号。  
> 来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/valid-parentheses  
> 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路梳理:(个人梳理)
    括号都是成对存在的,在从左向右进行解析的时候,可以将遍历的符号都存入到一个集合或者数组中;
    遇到了开括号,那就存放闭括号,
    遇到闭括号,那就存集合中获取最后存储的符号,看是否是一致的;
    若一致则有效,反之无效;
    因此使用一个可以后进先出的集合存储是最好的,因此选用 栈(Stack)

class Solution {
        
        public boolean isValid(String s) {
        
            Stack<Character> st = new Stack<>();
    
            for(int i = 0; i < s.length(); i ++) {
        
            	// 遇到开括号,存闭括号
                if (s.charAt(i) == '(') {
        
                    st.push(')');
                } else if (s.charAt(i) == '[') {
        
                    st.push(']');
                } else if (s.charAt(i) == '{') {
        
                    st.push('}');
                }else if (st.isEmpty() || st.pop() != s.charAt(i) ){
        
                	//闭括号取出比较
                	// 获取到了符号,但是栈中却没有,那肯定是闭括号,所以false
                	// 若不为空,且前面都有入栈,因此肯定是闭括号,出栈比较,相同就是没问题,不相同则无效
                   return false;
                }
            }
            return st.isEmpty();
        }
    }