LeetCode刷题day020 (Jieky)
程序员文章站
2022-06-21 13:55:22
LeetCode第20题/*Given a string containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.An input string is valid if:Open brackets must be closed by the same type of brackets. Open brackets must be closed in...
LeetCode第20题
/*
Given a string containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Note that an empty string is also considered valid.
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
*/
import java.util.*;
public class ValidParentheses{
public static void main(String[] args){
String str = "{[]}";
ValidParentheses vp = new ValidParentheses();
boolean result = vp.isValid02(str);
System.out.println(result);
}
// 使用Character 比 String 效率更高
public boolean isValid02(String s){
if(s == null) return false;
if(s != null && s.length() == 0) return true;
HashMap<Character,Character> pairs = new HashMap<Character,Character>();
pairs.put(')','(');
pairs.put(']','[');
pairs.put('}','{');
Stack<Character> elements = new Stack<Character>();
// 将字符串转为字符数组
char[] array = s.toCharArray();
for (int i=0;i<s.length();i++){
char temp = array[i];
// 左括号入栈
if (temp == '(' || temp == '{' || temp == '['){
elements.push(temp);
// 右括号校对栈顶元素是否匹配,匹配则栈顶元素出栈(包装类和基本类型可以自动转换)
}else if(!elements.empty() && pairs.get(temp) == elements.peek()){
elements.pop();
// 当前右括号和栈顶元素不匹配,或栈为空且还有右括号
}else{
return false;
}
}
// 查看栈是否为空,栈里面不可能有右括号,主要查看是否还有左括号
if(elements.empty()){
return true;
}else{
return false;
}
}
public boolean isValid01(String s){
if(s == null) return false;
if(s != null && s.length() == 0) return true;
HashMap<String,String> pairs = new HashMap<String,String>();
pairs.put(")","(");
pairs.put("}","{");
pairs.put("]","[");
Stack<String> elements = new Stack<String>();
String temp = null;
for (int i=0;i<s.length();i++){
temp = s.substring(i,i+1);
// 左括号入栈
if (temp.equals("(") || temp.equals("{") || temp.equals("[")){
elements.push(temp);
// 右括号校对栈顶元素是否匹配,匹配则栈顶元素出栈
}else if(!elements.empty() && pairs.get(temp).equals(elements.peek())){
elements.pop();
// 当前右括号和栈顶元素不匹配,或栈为空且还有右括号
}else{
return false;
}
}
// 查看栈是否为空,栈里面不可能有右括号,主要查看是否还有左括号
if(elements.empty()){
return true;
}else{
return false;
}
}
}
本文地址:https://blog.csdn.net/qq_24964575/article/details/112254484
上一篇: Java入门知识接口与抽象类的区别
下一篇: Java 面试宝典