前言
新的一年，好好学习。
正文
问题来源
本问题来自leetcode上的20题。
问题描述
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1：
输入: "([)]"
输出: false
示例 2：
输入: "{[]}"
输出: true
分析：
1.初始化栈 S。 2.一次处理表达式的每个括号。 3.如果遇到开括号，我们只需将其推到栈上即可。这意味着我们将稍后处理它，让我们简单地转到前面的 子表达式。 4.如果我们遇到一个闭括号，那么我们检查栈顶的元素。如果栈顶的元素是一个 相同类型的左括号，那么我们将它从栈中弹出并继续处理。否则，这意味着表达式无效。 5.如果到最后我们剩下的栈中仍然有元素，那么这意味着表达式无效。
func isValid(s string) bool {
sl := len(s)
stack := make([]byte, 0, sl)
for i := 0; i < sl; i++ {
//可以将匹配规则存入map中
if s[i] == ')' || s[i] == '}' || s[i] == ']' {
l := len(stack)
if l > 0 {
t := stack[l-1]
stack = stack[:l-1]
if (t == '(' && s[i] == ')') || (t == '{' && s[i] == '}') || (t == '[' && s[i] == ']') {
continue
}
return false
} else {
return false
}
} else {
stack = append(stack, s[i])
}
}
//可以改为 return len(stack) == 0
if len(stack) > 0 {
return false
}
return true
}
Java题解
class Solution {
// Hash table that takes care of the mappings.
private HashMap<Character, Character> mappings;
// Initialize hash map with mappings. This simply makes the code easier to read.
public Solution() {
this.mappings = new HashMap<Character, Character>();
this.mappings.put(')', '(');
this.mappings.put('}', '{');
this.mappings.put(']', '[');
}
public boolean isValid(String s) {
// Initialize a stack to be used in the algorithm.
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// If the current character is a closing bracket.
if (this.mappings.containsKey(c)) {
// Get the top element of the stack. If the stack is empty, set a dummy value of '#'
char topElement = stack.empty() ? '#' : stack.pop();
// If the mapping for this bracket doesn't match the stack's top element, return false.
if (topElement != this.mappings.get(c)) {
return false;
}
} else {
// If it was an opening bracket, push to the stack.
stack.push(c);
}
}
// If the stack still contains elements, then it is an invalid expression.
return stack.isEmpty();
}
}
总结：
勤思考。
结语
不管怎么样好好加油。
