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

LeetCode刷题:20. Valid Parentheses

程序员文章站 2024-03-16 12:59:10
...

LeetCode刷题:20. Valid Parentheses

原题链接:https://leetcode.com/problems/valid-parentheses/


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


算法设计

package com.bean.algorithm.basic;

import java.util.Stack;

public class ValidParentheses {

	public boolean isValid(String s) {
		if (s == "" || s.isEmpty())
			return true;
		Stack stack = new Stack();

		for (int index = 0; index < s.length(); index++) {
			char ch = s.charAt(index);

			if (ch == '(' || ch == '[' || ch == '{') {
				stack.push(ch);
			} else {
				char expected;
				if (ch == ')')
					expected = '(';
				else if (ch == ']')
					expected = '[';
				else
					expected = '{';

				if (stack.isEmpty()) {
					return false;
				}

				char actual = (char) stack.pop();
				if (actual != expected) {
					return false;
				}
			}
		}

		return stack.isEmpty();
	}
	
	public static void main(String[] args) {
		
		ValidParentheses vp=new ValidParentheses();
		
		//String input="()[]{}";
		String input="([)]";
		
		boolean flag=vp.isValid(input);
		System.out.println("flag is: "+flag);
	}

}

程序运行结果:

当 input = “()[]{}”时,返回 flag = true;

当 input = “([)]”时,返回 flag = false