[LeetCode] 20. Valid Parentheses

轉自LeetCode

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

<Solution>

這題不難，典型的 stack 解法

code 如下

C++

	class Solution {
	public:
	bool isValid(string s) {
	stack<char> myStack;
	for(auto c : s) {
	if(c == '(' || c == '{' || c == '[') {
	myStack.push(c);
	}
	else {
	//> ),},] come before (,{,[
	if(myStack.empty()) {
	return false;
	}
	//> match
	if((c == ')' && myStack.top() == '(') ||
	(c == '}' && myStack.top() == '{') ||
	(c == ']' && myStack.top() == '[')) {
	myStack.pop();
	}
	else {
	return false;
	}
	}
	}
	return myStack.empty();
	}
	};

view raw validParentheses.cpp hosted with ❤ by GitHub

Java

	public class Solution {
	public boolean isValid(String s) {
	Stack<Character> stack = new Stack<>();
	for(char c : s.toCharArray()) {
	if(c == '(') {
	stack.push(')');
	}
	else if(c == '{') {
	stack.push('}');
	}
	else if(c == '[') {
	stack.push(']');
	}
	else if(stack.empty() || stack.pop() != c) {
	return false;
	}
	}
	return stack.empty();
	}
	}

view raw validParentheses.java hosted with ❤ by GitHub

kotlin

	class Solution {
	fun isValid(s: String): Boolean {
	val stack = mutableListOf<Char>()
	var last: Char?
	for (c in s) {
	if (c == ')' || c == '}' || c == ']') {
	last = stack.lastOrNull()
	when {
	c == ')' && last == '(' -> {
	stack.removeAt(stack.lastIndex)
	}
	c == '}' && last == '{' -> {
	stack.removeAt(stack.lastIndex)
	}
	c == ']' && last == '[' -> {
	stack.removeAt(stack.lastIndex)
	}
	else -> return false
	}
	} else {
	stack.add(c)
	}
	}
	return stack.isEmpty()
	}
	}

view raw valid_parentheses.kt hosted with ❤ by GitHub