LeetCode刷题：20. Valid Parentheses

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