本文共 1487 字，大约阅读时间需要 4 分钟。

LeetCode刷题：20. 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

 

转载地址：http://sntdi.baihongyu.com/