Leetcode刷题100天—20. 有效的括号（栈）—day02

忘是亡心i 2022-08-29 10:08 151阅读 0赞

前言：

> 作者：神的孩子在歌唱  
> 大家好，我叫运智

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjY1NDExNA_size_16_color_FFFFFF_t_70]

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

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

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

**示例 1：**

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

**示例 2：**

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

**示例 3：**

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

**示例 4：**

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

**示例 5：**

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

**提示：**

1 <= s.length <= 104
    s 仅由括号 '()[]{}' 组成

> 来源：力扣（LeetCode）  
> 链接：https://leetcode-cn.com/problems/valid-parentheses  
> 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

### 代码 ###

package 栈;
    import java.util.HashMap;
    import java.util.Stack;
    /* * 1 * https://leetcode-cn.com/problems/valid-parentheses/ * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。 */
    public class _20_有效的括号 { 
    // 方法一：遍历字符串，如果找到匹配的就删除。耗性能
    	public boolean isValid(String s) { 
    		while (s.contains("{}")||s.contains("[]")||s.contains("()")) { 
    			s=s.replace("{}","");
    			s=s.replace("[]","");
    			s=s.replace("()","");
    		}
    // 如果是空就返回true，否则就false
    		return s.isEmpty();
    	}
    // 方法二：通过栈判断
    	public boolean isValid2(String s) { 
    // new一个栈，泛型不能直接放基本输出类型char，只能放char对应的包装类Character
    		Stack<Character> stack=new Stack<>();
    		int len=s.length();
    		for (int i=0;i<len;i++) { 
    			char c=s.charAt(i);
    			if(c=='(' || c=='{'|| c=='[') { //左括号
    // 将左括号的字符push进栈
    				stack.push(c);
    			}else { //右括号
    				if (stack.isEmpty()) return false;
    // 如果发现右括号就pop出来对比，比如栈里面有{，pop出来是栈顶的数}
    				char left=stack.pop();
    // 如果不匹配就返回false
    				if (left=='('&& c!=')') return false;
    				if (left=='{'&& c!='}') return false;
    				if (left=='['&& c!=']') return false;
    			}
    		}
    // 如果栈空说明全部匹配，返回true
    		return stack.isEmpty();
    	}
    // 通过字典哈希map
    	private static HashMap<Character, Character> map=new HashMap<>();
    // public _20_有效的括号() { 
    // //key-value
    // map.put('(', ')');
    // map.put('{', '{');
    // map.put('[', ']');
    // }
    	static { 
    		//key-value
    		map.put('(', ')');
    		map.put('{', '{');
    		map.put('[', ']');
    	}
    // 通过栈判断
    	public boolean isValid3(String s) { 
    // new一个栈，泛型不能直接放基本输出类型char，只能放char对应的包装类Character
    		Stack<Character> stack=new Stack<>();
    		int len=s.length();
    		for (int i=0;i<len;i++) { 
    			char c=s.charAt(i);
    			if(map.containsKey(c)) { //左括号
    // 将左括号的字符push进栈
    				stack.push(c);
    			}else { //右括号
    				if (stack.isEmpty()) return false;
    // 如果发现右括号就pop出来对比，比如栈里面有{，pop出来是栈顶的数}
    				char left=stack.pop();
    // 如果不匹配就返回false
    				if(c!=map.get(left)) return false;
    			}
    		}
    // 如果栈空说明全部匹配，返回true
    		return stack.isEmpty();
    	}	
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114  
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjY1NDExNA_size_16_color_FFFFFF_t_70]: /images/20220829/fa7250e8770b42d6980ba17481cc282f.png