Open Shawngbk opened 7 years ago
伪代码 输入：括号字符串，仅仅包含 (]} 这三种括号。 输入：输入的括号字符串是不是合法的，合法的输出true，不合法输出false。 字符指针i = 0 判断当前字符charAt（i），如果为［｛（则压入stack，如果为）｝］则检查peek（）符号，匹配则pop（）。
复杂度分析 很容易看出来括号字符串的每个字符都只需要考虑一遍，时间复杂度是O(n) public class Solution { public boolean isValid(String s) { Stack stack = new Stack (); 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 (s.charAt(i) == ')' && !stack.empty() && stack.peek() == '(') { stack.pop(); } else if (s.charAt(i) == ']' && !stack.empty() && stack.peek() == '[') { stack.pop(); } else if (s.charAt(i) == '}' && !stack.empty() && stack.peek() == '{') { stack.pop(); } else { return false; } } return stack.empty(); } }
伪代码 输入：括号字符串，仅仅包含 (]} 这三种括号。 输入：输入的括号字符串是不是合法的，合法的输出true，不合法输出false。 字符指针i = 0 判断当前字符charAt（i），如果为［｛（则压入stack，如果为）｝］则检查peek（）符号，匹配则pop（）。
复杂度分析 很容易看出来括号字符串的每个字符都只需要考虑一遍，时间复杂度是O(n) public class Solution { public boolean isValid(String s) { Stack stack = new Stack ();
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 (s.charAt(i) == ')' && !stack.empty() && stack.peek() == '(') {
stack.pop();
} else if (s.charAt(i) == ']' && !stack.empty() && stack.peek() == '[') {
stack.pop();
} else if (s.charAt(i) == '}' && !stack.empty() && stack.peek() == '{') {
stack.pop();
} else {
return false;
}
}
return stack.empty();
}
}