package LeetCode;

import java.util.Stack;

public class LeetCode20 {

// 20. Valid Parentheses

// https://leetcode.com/problems/valid-parentheses/description/

// 时间复杂度: O(n)

// 空间复杂度: O(n)

public boolean isValid(String s) {

Stack<Character> stack = new Stack<Character>();

for (int i = 0; i < s.length(); i++)

if (s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '[')

stack.push(s.charAt(i));

else {

if (stack.size() == 0)

return false;

Character c = stack.pop();

Character match;

if (s.charAt(i) == ')')

match = '(';

else if (s.charAt(i) == ']')

match = '[';

else {

assert s.charAt(i) == '}';

match = '{';

}

if (c != match)

return false;

}

if (stack.size() != 0)

return false;

return true;

}

}