问题
https://leetcode.com/problems/valid-parentheses/description/
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:
1 2
|
Input: "()" Output: true
|
Example 2:
1 2
|
Input: "()[]{}" Output: true
|
思路
使用Stack
后进先出的特点,对于入栈的符号查看栈顶是否配对,配对则移除栈顶元素,否则入栈,最终查看栈是否为空,有两种实现方式。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
|
public boolean (String s) { if (s == null || s.length() == 0) { return true; } Stack<Character> stack = new Stack<>(); for (int i = 0; i < s.length(); i ++) { Character topChar = stack.isEmpty() ? null : stack.peek(); char curChar = s.charAt(i); if (topChar != null) { if (topChar.charValue() == '(') { if (curChar == ')') { stack.pop(); continue; } } else if (topChar.charValue() == '{') { if (curChar == '}') { stack.pop(); continue; } } else if (topChar.charValue() == '[') { if (curChar == ']') { stack.pop(); continue; } } } stack.push(Character.valueOf(curChar)); } return stack.isEmpty(); }
public boolean isValid2(String s) { Stack<Character> stack = new Stack<Character>(); for (char c : s.toCharArray()) { if (c == '(') { stack.push(')'); } else if (c == '{') { stack.push('}'); } else if (c == '[') { stack.push(']'); } else if (stack.isEmpty() || stack.pop() != c) { return false; } } return stack.isEmpty(); }
|
近期评论