欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

相关标签: LeetCode java