Codility : Brackets 确定给定的括号字符串是否正确嵌套
Codility : Brackets Determine whether a given string of parentheses is properly nested
来自codility的问题描述：
一个由N个字符组成的字符串S，如果满足以下任一条件，则认为是正确嵌套的：
S为空；
S 的形式为“(U)”或“[U]”或“{U}”，其中 U 是正确嵌套的字符串；
S 的形式为 "VW"，其中 V 和 W 是正确嵌套的字符串。
例如，字符串“{[()()]}”是正确嵌套的，但“([)()]”不是。
写一个函数：
class 解决方案 { public int 解决方案（字符串 S）； }
给定一个由 N 个字符组成的字符串 S，return如果 S 正确嵌套则为 1，否则为 0。
例如，给定 S = "{[()()]}"，函数应该 return 1 并且给定 S = "([)()]"，函数应该 return 0，如上所述。
假设：
N为[0..200,000]范围内的整数；
字符串 S 仅由以下字符组成：“(”、“{”、“[”、“]”、“}” and/or “)”。
复杂度：
预期的最坏情况时间复杂度为 O(N)；
预期的最坏情况 space 复杂度为 O(N)（不计算输入参数所需的存储空间）。
我得到 87% 我似乎无法弄清楚问题。
这是我的代码：
// you can also use imports, for example:
// import java.util.*;
import java.util.Stack;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(String s) {
if (s.length() % 2 != 0) {
return 0;
}
Character openingBrace = new Character('{');
Character openingBracket = new Character('[');
Character openingParen = new Character('(');
Stack<Character> openingStack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == openingBrace || c == openingBracket || c == openingParen) {
openingStack.push(c);
} else {
if (i == s.length()-1 && openingStack.size() != 1) {
return 0;
}
if (openingStack.isEmpty()) {
return 0;
}
Character openingCharacter = openingStack.pop();
switch (c) {
case '}':
if (!openingCharacter.equals(openingBrace)) {
return 0;
}
break;
case ']':
if (!openingCharacter.equals(openingBracket)) {
return 0;
}
break;
case ')':
if (!openingCharacter.equals(openingParen)) {
return 0;
}
break;
default:
break;
}
}
}
return 1;
}
}
对于此类错误，最好的办法是坐下来编写一些单元测试（JUnit 是一个很好的框架）来验证您对算法工作原理的理解。
在这种情况下，由于 Trengot 已经计算出 "negative_match" 输入是 ))((，您至少需要这些测试用例：
))(( : 这是你的基础测试，一旦通过你就满足了要求，至少可以宣布部分胜利。}}{{ : 这是一般错误，还是只与错误处理特定字符有关？})({ : 是跟重复字符有关，还是混合输入也有？(}{) ：这是与在字符串开头有一个开始标记相关的边缘情况，还是这种行为更普遍？
一旦你理解了它实际上在做什么，而不是你的大脑告诉你它在做什么（你的大脑会撒谎告诉你这个），修复它应该相当简单。
右括号块中的第一个条件检查堆栈的大小是否为 != 1。我认为这是为了检查您没有任何剩余的左括号，这是个好主意。但是，如果您的最后一个字符不是结束符 bracket/paren/..
，您将错过整个检查
例如，对于 ((( 这样的输入，这会失败。
一个简单的修复方法是在循环结束后检查堆栈是否确实为空。
所以根据 Leeor 的建议，这是一个 100% 的解决方案
// you can also use imports, for example:
// import java.util.*;
import java.util.Stack;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(String s) {
if (s.length() % 2 != 0) {
return 0;
}
Character openingBrace = new Character('{');
Character openingBracket = new Character('[');
Character openingParen = new Character('(');
Stack<Character> openingStack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == openingBrace || c == openingBracket || c == openingParen) {
openingStack.push(c);
} else {
if (openingStack.isEmpty()) {
return 0;
}
Character openingCharacter = openingStack.pop();
switch (c) {
case '}':
if (!openingCharacter.equals(openingBrace)) {
return 0;
}
break;
case ']':
if (!openingCharacter.equals(openingBracket)) {
return 0;
}
break;
case ')':
if (!openingCharacter.equals(openingParen)) {
return 0;
}
break;
default:
break;
}
}
}
if (!openingStack.isEmpty()) {
return 0;
}
return 1;
}
}
代码：06:12:11 UTC，c，决赛，分数：100.00
int solution(char *S) {
// write your code in C99
int len;
if((len=strlen(S))==0) return 1;
char stuck[len];
char open[]="([{";
char close[]=")]}";
int top=0;
for (int i=0;i<len;i++)
{
if (strchr(open,S[i])!=NULL)
{
stuck[top]=S[i];
top++;
}
else if (strchr(close,S[i])!=NULL)
{
if ((top>0)&&((strchr(open,stuck[top-1])-open)==(strchr(close,S[i])-close)))
top--;
else
return 0;
}
}
if (top==0)
return 1;
return 0;
}
100% 简单 JavaScript 解决方案
function solution(S) {
S = S.split("");
var stack = [];
for (var i = 0; i < S.length; i++) {
var c = S[i];
if (c == '{' || c == '(' || c == '[')
stack.push(c);
else if (c == '}' || c == ')' || c == ']') {
var t = stack.pop() + c;
if (t != "{}" && t != "()" && t != "[]")
return 0;
}
else
return 0;
}
if (stack.length > 0)
return 0;
return 1;
}
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
class Solution {
public static final int BALANCED = 1;
public static final int UNBALANCED = 0;
public int solution(String S) {
if (S.isEmpty()) return BALANCED;
Stack<Character> stack = new Stack<>(S.length());
NestedValidatorUtil util = new NestedValidatorUtil();
for (char c: S.toCharArray()) {
if (stack.isEmpty()){
if (util.isOpener(c)) {
stack.push(c);
} else {
return UNBALANCED;
}
} else {
if(util.isOpener(c)) {
stack.push(c);
} else if(util.getOpenerForGivenCloser(c) == stack.peek()){
stack.pop();
} else {
return UNBALANCED;
}
}
}
return stack.isEmpty() ? BALANCED : UNBALANCED;
}
public static class NestedValidatorUtil {
private Map<Character, Character> language = new HashMap<Character, Character>(){{
put(')','(');
put(']','[');
put('}','{');
}};
public boolean isOpener(Character c) {
return language.values().contains(c);
}
public Character getOpenerForGivenCloser(Character closer) {
return language.get(closer);
}
}
public static class Stack<T> {
public List<T> stack;
public Stack(int capacity) {
stack = new ArrayList<>(capacity);
}
public void push(T item) {
stack.add(item);
}
public T pop() {
T item = peek();
stack.remove(stack.size() - 1);
return item;
}
public T peek() {
int position = stack.size();
T item = stack.get(position - 1);
return item;
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
}
Here's a link to the code。希望对你有帮助。
在 java 中通过了 100/100 的适应性测试。
public static int solution(String S){
Stack<Character> stack = new Stack<Character>();
if(null == S){
return 0;
}else if(S.isEmpty()){
return 1;
}
for (Character C : S.toCharArray()) {
switch (C) {
case ')':
pops(stack, '(');
break;
case '}':
pops(stack, '{');
break;
case ']':
pops(stack, '[');
break;
default:
stack.push(C);
break;
}
}
return stack.isEmpty() ? 1 : 0;
}
private static void pops(Stack<Character> s, Character C){
while(!s.isEmpty() && s.peek() != C){
s.pop();
}
if(!s.isEmpty()){
s.pop();
}else{
s.push(C);
}
}
这里有我在 java 中的 100% 解决方案：
https://codility.com/demo/results/training2C7U2E-XM3/
/**
* https://codility.com/demo/results/training2C7U2E-XM3/ 100%
*
* Problem facts:
* 1) A string S consisting of N characters is given
* 2) S is properly nested if:
* -S is empty;
* -S has the form "(U)" or "[U]" or "{U}" where U is a properly nested string;
* -S has the form "VW" where V and W are properly nested strings.
* 3) N is an integer within the range [0..200,000];
* 4) string S consists only of the following characters: "(", "{", "[", "]", "}" and/or ")".
* 5) expected worst-case time complexity is O(N);
* 6) expected worst-case space complexity is O(N)
*
* Solution:
* The idea is to iterate over the string and push opening brackets, then each time a closing bracket appears
* it will be matched with the last opening match stacked, if both are of the same type, then pop that char,
* otherwise return 0.
* If the string S is properly nested the remaining stack will be empty.
*
* There are three cases to analize:
* 1) The stack is empty, push the first char.
* 2) The stack is not empty, peek the last char and it is the opening bracket of current closing bracket, then
* pop the char from the stack.
* 3) The stack is not empty, peek the last char and it isn't the opening bracket of current closing bracket,
* return 0, because the string is malformed.
*
* @param S
* @return 1 if S is properly nested and 0 otherwise.
*/
public static int solution(String S) {
if(S.isEmpty()) return 1; // pay attention to corner case 1
if(S.length()==1) return 0; // and 2
Stack<Character> stack = new Stack<>();
for(int i=0; i<S.length(); i++) {
char current = S.charAt(i);
switch (current) {
case '}':
if (!stack.isEmpty() && stack.peek() == '{') {
stack.pop();
}
else return 0;
break;
case ']':
if (!stack.isEmpty() && stack.peek() == '[') {
stack.pop();
}
else return 0;
break;
case ')':
if (!stack.isEmpty() && stack.peek() == '(') {
stack.pop();
}
else return 0;
break;
default:
stack.push(current);
break;
}
}
return stack.size()==0 ? 1 : 0;
}
这是我的 C# 简单解决方案，它获得了 100% 的正确性和 100% 的性能。时间复杂度为 O(N)。
https://codility.com/demo/results/trainingRVS3SF-DC6/
using System;
using System.Collections.Generic;
class Solution {
public int solution(string S) {
// Return 1 if string size is 0
if(S.Length==0) return 1;
Stack<char> brackets = new Stack<char>();
foreach(char c in S){
if(c=='['||c=='{'||c=='('){
brackets.Push(c);
}
else{
// return 0 if no opening brackets found and
// first bracket is a closing bracket
if(brackets.Count==0) return 0;
if(c==')'){
if(brackets.Peek()=='(') brackets.Pop();
else return 0;
}
if(c=='}'){
if(brackets.Peek()=='{') brackets.Pop();
else return 0;
}
if(c==']'){
if(brackets.Peek()=='[') brackets.Pop();
else return 0;
}
}
}
if(brackets.Count==0) return 1;
return 0;
}
}
我在 java 中使用以下解决方案获得了 100% 的成功。时间复杂度为O(N)
class Solution {
public int solution(String S) {
char[] charArray=S.toCharArray();
//This array works as stack
char[] stack=new char[charArray.length];
//currently stack is empty
int stackSize=0;
for(int i=0;i<charArray.length;i++){
//Check start characters and add it to stack
if(charArray[i]=='{' ||charArray[i]=='(' || charArray[i]=='['){
stack[stackSize++]=charArray[i];
}else{
//This section checks for end character.
//End characters with stack being empty confirms not nested
if(stackSize==0){
result=0;
break;
}
//Pop stack
char ch=stack[--stackSize];
//check
if((charArray[i]=='}' && ch=='{') || (charArray[i]==']' && ch=='[') ||(charArray[i]==')' && ch=='(')){
continue;
}else{
//if pop character not matching, confirms non nesting
result=0;
break;
}
}
}
//if stack is not empty indicates non nested, otherwise result
return stackSize==0?result:0;
}
}
@Moxi 和@Caesar Avgvstvs 的回答启发了我。
但我相信我的更短，没有遗漏任何东西。
我的解决方案在 codility 中通过了 100%。我使用 Map 来避免重复。这是我在 Java.
中的解决方案
import java.util.*;
public static int solution(String S) {
if (S.isEmpty()) return 1;
if (S.length() % 2 == 1) return 0; // the length cannot be an odd number.
// in time complexity this decreases from O(n) to O(1).
// this Map avoid the ugly "switch case"
Map<Character, Character> map = new HashMap<Character, Character>();
map.put('}', '{');
map.put(')', '(');
map.put(']', '[');
Stack<Character> stack = new Stack<Character>();
for (Character c : S.toCharArray()) {
if (map.containsKey(c)) {
if (!stack.isEmpty() && map.get(c) == stack.peek()) {
stack.pop();
} else {
return 0;
}
} else {
stack.push(c);
}
}
return stack.isEmpty() ? 1 : 0;
}
100% Java
public int solution(String S) {
Stack<Character> stack = new Stack<>();
for(int i=0; i<S.length(); i++) {
char c = S.charAt(i);
if (c == '[' || c == '{' || c == '(' || c == 'V') {
stack.push(c);
} else if (c == ']' || c == '}' || c == ')' || c == 'W') {
if (checkBracket(stack, c)) {
stack.pop();
} else {
return 0;
}
} else {
return 0;
}
}
if (stack.empty()) {
return 1;
}
return 0;
}
private boolean checkBracket(Stack<Character> stack, char bracket) {
if (stack.empty()) return false;
char lastStackBracket = stack.peek();
if (lastStackBracket == '{' && bracket == '}') {
return true;
} else if (lastStackBracket == '[' && bracket == ']') {
return true;
} else if (lastStackBracket == '(' && bracket == ')') {
return true;
} else if (lastStackBracket == 'V' && bracket == 'W') {
return true;
}
return false;
}
当然需要导入java.util:
import java.util.*;
function solution(S) {
if (0 === S.length) {
return 1
}
let stack = []
for (let i = 0; i < S.length; i++) {
if ('(' === S[i] || '{' === S[i] || '[' === S[i]) {
stack.push(S[i])
} else {
let couple = [stack.pop(), S[i]].join('')
if ('()' !== couple && '{}' !== couple && '[]' !== couple) {
return 0
}
}
}
if (stack.length) {
return 0
}
return 1
}
我在 Swift 中的解决方案。应该可以正常工作
public func Brackets(_ S : inout String) -> Int {
var Stack = [Character]()
let matching : [Character:Character] = ["(":")", "[":"]", "{":"}"]
for s in S {
let char = S.removeFirst()
if "({[".contains(char) {
print(char)
Stack.append(char)
}
if( "]})".contains(char)) {
print(char)
let bracket = Stack.removeLast()
if matching[bracket] != char {
return 0
}
}
}
return 1
}
var S1 = "{[()()]}"
var S2 = "([)()]"
print("Brackets: ", Brackets(&S1))
print("Brackets: ", Brackets(&S2))
简单java解决方案，100/100
public int solution(String S) {
Deque<Character> stack = new ArrayDeque<Character>();
for(int i = 0; i < S.length(); i++) {
char c = S.charAt(i);
switch (c) {
case ')':
if (stack.isEmpty() || stack.pop() != '(')
return 0;
break;
case ']':
if (stack.isEmpty() || stack.pop() != '[')
return 0;
break;
case '}':
if(stack.isEmpty() || stack.pop() != '{')
return 0;
break;
default:
stack.push(c);
break;
}
}
return stack.isEmpty() ? 1 : 0;
}
我知道这与您的问题没有直接关系。
但是我有一个有效的解决方案，运行 时间复杂度为 O(N)，space 复杂度为 O(1)。
该解决方案在 codility 中获得 100/100。
用 C++ 编写：
int solution(string S) {
int N = S.size();
if(N == 0) return 1;//empty string is properly nested
if(S[0] == ')' || S[0] == ']' || S[0] == '}' ) return 0;// a properly nested string cannot beging with those chars
if(S[N-1] == '(' || S[N-1] == '[' || S[N-1] == '{' ) return 0; // cannot end with those chars
int paren_open = 0;
int brac_open = 0;
int curl_open = 0;
for(int i =0 ; i < N;++i){
if(S[i] == ')' && (paren_open == 0 || S[i-1] == '[' || S[i-1] == '{')) return 0; //expected opening but got closing
if(S[i] == ']' && (brac_open == 0 || S[i-1] == '(' || S[i-1] == '{')) return 0; //same here
if(S[i] == '}' && (curl_open == 0 || S[i-1] == '[' || S[i-1] == '(')) return 0; //same here
if(S[i] == '(') paren_open++;
else if(S[i] == ')') paren_open--;
else if(S[i] == '[') brac_open++;
else if(S[i] == ']') brac_open--;
else if(S[i] == '{') curl_open++;
else if(S[i] == '}') curl_open--;
}
if(paren_open == 0 && brac_open == 0 && curl_open ==0)
return 1;
return 0; }
找不到任何 python 脚本...但它就在这里！尽量保持简单。
def solution(S):
# write your code in Python 3.6
arr = []
if len(S) < 1:
return 1
if not isinstance(S, str):
return 0
for i in range(0, len(S)):
# print(S[i])
if startSym(S[i]):
arr.append(value(S[i]))
# print(arr)
elif endSym(S[i]):
if len(arr) > 0 and value(S[i]) == arr[len(arr) - 1]:
# print(S[i])
# print(arr)
del arr[len(arr) - 1]
else:
return 0
else:
return 0
if len(arr) == 0:
return 1
else:
return 0
def startSym(x):
if x == '{' or x == '[' or x == '(':
return True
else:
return False
def endSym(x):
if x == '}' or x == ']' or x == ')':
return True
else:
return False
def value(x):
if x == '{' or x == '}':
return 1
if x == '[' or x == ']':
return 2
if x == '(' or x == ')':
return 3
此问题的简洁明了 Python 解决方案。 Codility 100%
def solution(S):
matches, stack = dict(['()', '[]', '{}']), []
for i in S:
if i in matches.values():
if stack and matches[stack[-1]] == i:
stack.pop()
else:
return 0
else:
stack.append(i)
return int(not stack)
Ruby 100%
def solution(s)
s.split('').inject([]) do |stack, el|
next stack.push(el) if ['[', '{', '('].include?(el)
current = stack.pop
next stack if (current == '{' && el == '}') ||
(current == '(' && el == ')') ||
(current == '[' && el == ']')
return 0
end.empty? ? 1 : 0
end
这是 python 中的解决方案，在 Codility
处为 100%
我添加了一些解释和步骤，希望这对任何人有帮助...
Idea
Idea is to use stack concept
Used array [] as stack
Keep adding item in stack until open brackets found, Keep popping up item if closing bracket found.
On each pop of item check popped item it should match with the opposite bracket as explained in example else not balanced.
Operation
4 push 4 pop
{[()()]}
push {
push [
push (
pop )
push (
pop )
pop ]
pop }
gets empty
2 push 1 pop
([)()]
(
[
) - not matching with [ so not balanced
代码-
def solution(S):
stack = []
for bracket in S:
# open bracket found push in to stack, used array as stack append item at top
if bracket == "{" or bracket == "[" or bracket == "(":
stack.append(bracket)
# any closing bracket found and stack is not empty remote item from stack top
elif bracket == "}" and stack:
pop_item = stack.pop()
# check popped item, if it is not similar( ie. opposite or open) as bracket then this S can not be balanced
if pop_item != "{":
return 0
elif bracket == "]" and stack:
pop_item = stack.pop()
if pop_item != "[":
return 0
elif bracket == ")" and stack:
pop_item = stack.pop()
if pop_item != "(":
return 0
# at any point if neither open nor close operation can be performed, stack is not balanced
else:
return 0
print(stack)
# if stack is empty stack, it is balanced ie. all push and pop operation on S is successful¬.
if not stack:
return 1
# S is not balanced
return 0
if __name__ == '__main__':
# result = solution("{[()()]}")
result = solution("([)()]")
print("")
print("Solution " + str(result))
运行 测试用例 -
['{']
['{', '[']
['{', '[', '(']
['{', '[']
['{', '[', '(']
['{', '[']
['{']
[]
Solution 1
['(']
['(', '[']
Solution 0
这里是Java100%
public int solution(String S) {
// write your code in Java SE 8
List open = Arrays.asList('(', '{', '[');
List close = Arrays.asList(')', '}', ']');
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < S.length(); i++) {
if (open.contains(S.charAt(i))) {
stack.push(S.charAt(i));
} else if (close.contains(S.charAt(i)) && !stack.isEmpty()) {
Character top = stack.peek();
if (open.indexOf(top) == close.indexOf(S.charAt(i))) {
stack.pop();
} else {
return 0;
}
} else {
return 0;
}
}
return stack.isEmpty() ? 1 : 0;
}
我在 C# 中的 100% 解决方案。
using System;
using System.Collections.Generic;
using System.Linq;
class Solution {
private Dictionary<char,char> closing = new Dictionary<char,char>{{'}','{'},{')','('},{']','['}};
public int solution(string S) {
var stack = new Stack<char>();
foreach(var c in S)
{
if(!closing.Keys.Contains(c))
stack.Push(c);
else if(!stack.Any() || closing[c] != stack.Pop() )
return 0;
}
return !stack.Any() ? 1 : 0;
}
}
Python 中简单而详细的解决方案，得分为 100%
def solution(S):
if len(S) == 0:
return 1
opening = ["(", "{", "["]
closing = [")", "}", "]"]
ls_my_o = []
for s in S:
if s in opening:
ls_my_o.append(s)
elif s in closing:
if len(ls_my_o) < 1:
return 0
ele = ls_my_o.pop()
if opening.index(ele) != closing.index(s):
return 0
if len(ls_my_o) == 0:
return 1
return 0
Javascript 100% 解决方案
function solution(S) {
const stack = []
const obj = { ")": "(", "}": "{", "]": "[" }
for (i = 0; i < S.length; i++) {
if (S[i] === '(' || S[i] === '{' || S[i] === '[') {
stack.push(S[i])
} else {
const last = stack.pop()
if (obj[S[i]] !== last) return 0
}
}
return stack.length === 0 ? 1 : 0
}
这是一个简单的 Python 解决方案 (100%)：
# Brackets
def solution(S):
if not S:
return 1
stack = []
brackets = {"(": ")", "{": "}", "[": "]"}
for elem in S:
if elem in brackets:
stack.append(elem)
if elem in brackets.values():
if stack:
if elem == brackets[stack.pop()]:
continue
else:
return 0
else:
return 0
return 0 if stack else 1
Swift 5 (100%)
public func solution(_ S : inout String) -> Int {
var stack: [Character] = []
let pairFor: [Character: Character] = ["(":")",
"{":"}",
"[":"]"]
let opening: Set<Character> = ["(","{","["]
let closing: Set<Character> = [")","}","]"]
for char in S {
if opening.contains(char) {
stack.append(char)
} else if closing.contains(char) {
guard stack.isEmpty == false else {
return 0
}
let bracket = stack.removeLast()
if pairFor[bracket] != char {
return 0
}
}
}
return stack.isEmpty ? 1 : 0
}
PHP 准确率为 100% 的解决方案
$sa = str_split($S);
if(strlen($S) == 0){
return 1;
}
$count = count($sa);
$res =1;
$opening = ['{'=>'}','('=>')','['=>']'];
$array =['{'=>'}','}'=>'{',')'=>'(','('=>')','['=>']',']'=>'['] ;
$stack = [];
for($i =0;$i<$count;$i++){
if(isset($opening[$sa[$i]])){
array_push($stack,$sa[$i]);
}else{
if(count($stack) == 0){
return 0;
}
$v = array_pop($stack);
if($array[$sa[$i]] !== $v){
return 0;
}
}
}
if (sizeof($stack) != 0) return 0;
return 1;
C++ (100%)
#include <stack>
int solution(string &S) {
// write your code in C++14 (g++ 6.2.0)
auto N = S.size();
stack<char> ST;
for(decltype(N) i{0}; i < N; i++) {
if ((S[i] == '{') || (S[i] == '[') || (S[i] == '(')) {
ST.push(S[i]);
}
else {
if (ST.empty()) {
return false;
}
char top = ST.top();
ST.pop();
if ((S[i] == ')') && (top != '(')) {
return false;
}
if ((S[i] == ']') && (top != '[')) {
return false;
}
if ((S[i] == '}') && (top != '{')) {
return false;
}
}
}
return ST.empty();
}
class Solution {
public int solution(String S) {
// write your code in Java SE 8
Stack<Character> myStack = new Stack<Character>();
for(Character singleChar : S.toCharArray()){
if((singleChar.equals('(')) || (singleChar.equals('{')) || (singleChar.equals('['))){
myStack.push(singleChar);
}
else{
if(myStack.size() == 0){
System.out.println("Stack size");
return 0;
}
if(singleChar.equals(')')){
if(myStack.peek().equals('('))
myStack.pop();
else
return 0;
}
if(singleChar.equals('}')){
if(myStack.peek().equals('{'))
myStack.pop();
else
return 0;
}
if(singleChar.equals(']')){
if(myStack.peek().equals('['))
myStack.pop();
else
return 0;
}
}
}
if(myStack.size()==0)
return 1;
else
return 0;
}
}
我认为这是一个更具可读性的 Java 解决方案，得分为 100%：
https://app.codility.com/demo/results/trainingUY545E-2EQ/
import java.util.Stack;
public class Brackets {
public int solution(String S) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < S.length(); i++) {
if (!process(stack, S.charAt(i))) {
return 0;
}
}
return stack.empty() ? 1 : 0;
}
private boolean process(Stack<Character> stack, char ch) {
Character opener = getOpener(ch);
if (opener == null) {
stack.push(ch);
} else {
if (stack.empty()) {
return false;
}
char top = stack.peek();
if (opener.equals(top)) {
stack.pop();
} else {
return false;
}
}
return true;
}
private Character getOpener(char ch) {
switch (ch) {
case ')':
return '(';
case '}':
return '{';
case ']':
return '[';
default:
return null;
}
}
}
我的 %100 JAVA 解决方案
class Solution {
public int solution(String S) {
Stack<Character> myStack = new Stack<>();
char[] chars = S.toCharArray();
for (int i = 0; i < chars.length; i++) {
char coming = chars[i];
switch(coming){
case '(': case '{': case '[':
myStack.push(coming);
break;
case ')': case '}': case ']':
if(myStack.isEmpty())
return 0;
char popped = myStack.pop();
if(!isValidPair(coming, popped))
return 0;
}
}
if(!myStack.isEmpty())
return 0;
return 1;
}
private boolean isValidPair(char c, char s) {
return ((c == ')' && s == '(') || (c == '}' && s == '{') || (c == ']' && s == '['));
}
}
我的 100% JavaScript 时间复杂度为 O(N) 的解决方案：
function solution(S) {
const openingTags = {
'[': ']',
'{': '}',
'(': ')',
};
const stack = [];
for (const char of S) {
// if char is not an opening tag, it is a closing tag
if (openingTags.hasOwnProperty(char)) {
stack.push(char);
} else if (openingTags[stack.pop()] !== char) {
return 0;
}
}
return Number(stack.length < 1);
}
来自codility的问题描述：
一个由N个字符组成的字符串S，如果满足以下任一条件，则认为是正确嵌套的：
S为空； S 的形式为“(U)”或“[U]”或“{U}”，其中 U 是正确嵌套的字符串； S 的形式为 "VW"，其中 V 和 W 是正确嵌套的字符串。 例如，字符串“{[()()]}”是正确嵌套的，但“([)()]”不是。
写一个函数：
class 解决方案 { public int 解决方案（字符串 S）； }
给定一个由 N 个字符组成的字符串 S，return如果 S 正确嵌套则为 1，否则为 0。
例如，给定 S = "{[()()]}"，函数应该 return 1 并且给定 S = "([)()]"，函数应该 return 0，如上所述。
假设：
N为[0..200,000]范围内的整数； 字符串 S 仅由以下字符组成：“(”、“{”、“[”、“]”、“}” and/or “)”。 复杂度：
预期的最坏情况时间复杂度为 O(N)； 预期的最坏情况 space 复杂度为 O(N)（不计算输入参数所需的存储空间）。
我得到 87% 我似乎无法弄清楚问题。
这是我的代码：
// you can also use imports, for example:
// import java.util.*;
import java.util.Stack;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(String s) {
if (s.length() % 2 != 0) {
return 0;
}
Character openingBrace = new Character('{');
Character openingBracket = new Character('[');
Character openingParen = new Character('(');
Stack<Character> openingStack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == openingBrace || c == openingBracket || c == openingParen) {
openingStack.push(c);
} else {
if (i == s.length()-1 && openingStack.size() != 1) {
return 0;
}
if (openingStack.isEmpty()) {
return 0;
}
Character openingCharacter = openingStack.pop();
switch (c) {
case '}':
if (!openingCharacter.equals(openingBrace)) {
return 0;
}
break;
case ']':
if (!openingCharacter.equals(openingBracket)) {
return 0;
}
break;
case ')':
if (!openingCharacter.equals(openingParen)) {
return 0;
}
break;
default:
break;
}
}
}
return 1;
}
}
对于此类错误，最好的办法是坐下来编写一些单元测试（JUnit 是一个很好的框架）来验证您对算法工作原理的理解。
在这种情况下，由于 Trengot 已经计算出 "negative_match" 输入是 ))((，您至少需要这些测试用例：
))((: 这是你的基础测试，一旦通过你就满足了要求，至少可以宣布部分胜利。}}{{: 这是一般错误，还是只与错误处理特定字符有关？})({: 是跟重复字符有关，还是混合输入也有？(}{)：这是与在字符串开头有一个开始标记相关的边缘情况，还是这种行为更普遍？
一旦你理解了它实际上在做什么，而不是你的大脑告诉你它在做什么（你的大脑会撒谎告诉你这个），修复它应该相当简单。
右括号块中的第一个条件检查堆栈的大小是否为 != 1。我认为这是为了检查您没有任何剩余的左括号，这是个好主意。但是，如果您的最后一个字符不是结束符 bracket/paren/..
，您将错过整个检查例如，对于 ((( 这样的输入，这会失败。
一个简单的修复方法是在循环结束后检查堆栈是否确实为空。
所以根据 Leeor 的建议，这是一个 100% 的解决方案
// you can also use imports, for example:
// import java.util.*;
import java.util.Stack;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(String s) {
if (s.length() % 2 != 0) {
return 0;
}
Character openingBrace = new Character('{');
Character openingBracket = new Character('[');
Character openingParen = new Character('(');
Stack<Character> openingStack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == openingBrace || c == openingBracket || c == openingParen) {
openingStack.push(c);
} else {
if (openingStack.isEmpty()) {
return 0;
}
Character openingCharacter = openingStack.pop();
switch (c) {
case '}':
if (!openingCharacter.equals(openingBrace)) {
return 0;
}
break;
case ']':
if (!openingCharacter.equals(openingBracket)) {
return 0;
}
break;
case ')':
if (!openingCharacter.equals(openingParen)) {
return 0;
}
break;
default:
break;
}
}
}
if (!openingStack.isEmpty()) {
return 0;
}
return 1;
}
}
代码：06:12:11 UTC，c，决赛，分数：100.00
int solution(char *S) {
// write your code in C99
int len;
if((len=strlen(S))==0) return 1;
char stuck[len];
char open[]="([{";
char close[]=")]}";
int top=0;
for (int i=0;i<len;i++)
{
if (strchr(open,S[i])!=NULL)
{
stuck[top]=S[i];
top++;
}
else if (strchr(close,S[i])!=NULL)
{
if ((top>0)&&((strchr(open,stuck[top-1])-open)==(strchr(close,S[i])-close)))
top--;
else
return 0;
}
}
if (top==0)
return 1;
return 0;
}
100% 简单 JavaScript 解决方案
function solution(S) {
S = S.split("");
var stack = [];
for (var i = 0; i < S.length; i++) {
var c = S[i];
if (c == '{' || c == '(' || c == '[')
stack.push(c);
else if (c == '}' || c == ')' || c == ']') {
var t = stack.pop() + c;
if (t != "{}" && t != "()" && t != "[]")
return 0;
}
else
return 0;
}
if (stack.length > 0)
return 0;
return 1;
}
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
class Solution {
public static final int BALANCED = 1;
public static final int UNBALANCED = 0;
public int solution(String S) {
if (S.isEmpty()) return BALANCED;
Stack<Character> stack = new Stack<>(S.length());
NestedValidatorUtil util = new NestedValidatorUtil();
for (char c: S.toCharArray()) {
if (stack.isEmpty()){
if (util.isOpener(c)) {
stack.push(c);
} else {
return UNBALANCED;
}
} else {
if(util.isOpener(c)) {
stack.push(c);
} else if(util.getOpenerForGivenCloser(c) == stack.peek()){
stack.pop();
} else {
return UNBALANCED;
}
}
}
return stack.isEmpty() ? BALANCED : UNBALANCED;
}
public static class NestedValidatorUtil {
private Map<Character, Character> language = new HashMap<Character, Character>(){{
put(')','(');
put(']','[');
put('}','{');
}};
public boolean isOpener(Character c) {
return language.values().contains(c);
}
public Character getOpenerForGivenCloser(Character closer) {
return language.get(closer);
}
}
public static class Stack<T> {
public List<T> stack;
public Stack(int capacity) {
stack = new ArrayList<>(capacity);
}
public void push(T item) {
stack.add(item);
}
public T pop() {
T item = peek();
stack.remove(stack.size() - 1);
return item;
}
public T peek() {
int position = stack.size();
T item = stack.get(position - 1);
return item;
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
}
Here's a link to the code。希望对你有帮助。
在 java 中通过了 100/100 的适应性测试。
public static int solution(String S){
Stack<Character> stack = new Stack<Character>();
if(null == S){
return 0;
}else if(S.isEmpty()){
return 1;
}
for (Character C : S.toCharArray()) {
switch (C) {
case ')':
pops(stack, '(');
break;
case '}':
pops(stack, '{');
break;
case ']':
pops(stack, '[');
break;
default:
stack.push(C);
break;
}
}
return stack.isEmpty() ? 1 : 0;
}
private static void pops(Stack<Character> s, Character C){
while(!s.isEmpty() && s.peek() != C){
s.pop();
}
if(!s.isEmpty()){
s.pop();
}else{
s.push(C);
}
}
这里有我在 java 中的 100% 解决方案： https://codility.com/demo/results/training2C7U2E-XM3/
/**
* https://codility.com/demo/results/training2C7U2E-XM3/ 100%
*
* Problem facts:
* 1) A string S consisting of N characters is given
* 2) S is properly nested if:
* -S is empty;
* -S has the form "(U)" or "[U]" or "{U}" where U is a properly nested string;
* -S has the form "VW" where V and W are properly nested strings.
* 3) N is an integer within the range [0..200,000];
* 4) string S consists only of the following characters: "(", "{", "[", "]", "}" and/or ")".
* 5) expected worst-case time complexity is O(N);
* 6) expected worst-case space complexity is O(N)
*
* Solution:
* The idea is to iterate over the string and push opening brackets, then each time a closing bracket appears
* it will be matched with the last opening match stacked, if both are of the same type, then pop that char,
* otherwise return 0.
* If the string S is properly nested the remaining stack will be empty.
*
* There are three cases to analize:
* 1) The stack is empty, push the first char.
* 2) The stack is not empty, peek the last char and it is the opening bracket of current closing bracket, then
* pop the char from the stack.
* 3) The stack is not empty, peek the last char and it isn't the opening bracket of current closing bracket,
* return 0, because the string is malformed.
*
* @param S
* @return 1 if S is properly nested and 0 otherwise.
*/
public static int solution(String S) {
if(S.isEmpty()) return 1; // pay attention to corner case 1
if(S.length()==1) return 0; // and 2
Stack<Character> stack = new Stack<>();
for(int i=0; i<S.length(); i++) {
char current = S.charAt(i);
switch (current) {
case '}':
if (!stack.isEmpty() && stack.peek() == '{') {
stack.pop();
}
else return 0;
break;
case ']':
if (!stack.isEmpty() && stack.peek() == '[') {
stack.pop();
}
else return 0;
break;
case ')':
if (!stack.isEmpty() && stack.peek() == '(') {
stack.pop();
}
else return 0;
break;
default:
stack.push(current);
break;
}
}
return stack.size()==0 ? 1 : 0;
}
这是我的 C# 简单解决方案，它获得了 100% 的正确性和 100% 的性能。时间复杂度为 O(N)。 https://codility.com/demo/results/trainingRVS3SF-DC6/
using System;
using System.Collections.Generic;
class Solution {
public int solution(string S) {
// Return 1 if string size is 0
if(S.Length==0) return 1;
Stack<char> brackets = new Stack<char>();
foreach(char c in S){
if(c=='['||c=='{'||c=='('){
brackets.Push(c);
}
else{
// return 0 if no opening brackets found and
// first bracket is a closing bracket
if(brackets.Count==0) return 0;
if(c==')'){
if(brackets.Peek()=='(') brackets.Pop();
else return 0;
}
if(c=='}'){
if(brackets.Peek()=='{') brackets.Pop();
else return 0;
}
if(c==']'){
if(brackets.Peek()=='[') brackets.Pop();
else return 0;
}
}
}
if(brackets.Count==0) return 1;
return 0;
}
}
我在 java 中使用以下解决方案获得了 100% 的成功。时间复杂度为O(N)
class Solution {
public int solution(String S) {
char[] charArray=S.toCharArray();
//This array works as stack
char[] stack=new char[charArray.length];
//currently stack is empty
int stackSize=0;
for(int i=0;i<charArray.length;i++){
//Check start characters and add it to stack
if(charArray[i]=='{' ||charArray[i]=='(' || charArray[i]=='['){
stack[stackSize++]=charArray[i];
}else{
//This section checks for end character.
//End characters with stack being empty confirms not nested
if(stackSize==0){
result=0;
break;
}
//Pop stack
char ch=stack[--stackSize];
//check
if((charArray[i]=='}' && ch=='{') || (charArray[i]==']' && ch=='[') ||(charArray[i]==')' && ch=='(')){
continue;
}else{
//if pop character not matching, confirms non nesting
result=0;
break;
}
}
}
//if stack is not empty indicates non nested, otherwise result
return stackSize==0?result:0;
}
}
@Moxi 和@Caesar Avgvstvs 的回答启发了我。
但我相信我的更短，没有遗漏任何东西。 我的解决方案在 codility 中通过了 100%。我使用 Map 来避免重复。这是我在 Java.
中的解决方案import java.util.*;
public static int solution(String S) {
if (S.isEmpty()) return 1;
if (S.length() % 2 == 1) return 0; // the length cannot be an odd number.
// in time complexity this decreases from O(n) to O(1).
// this Map avoid the ugly "switch case"
Map<Character, Character> map = new HashMap<Character, Character>();
map.put('}', '{');
map.put(')', '(');
map.put(']', '[');
Stack<Character> stack = new Stack<Character>();
for (Character c : S.toCharArray()) {
if (map.containsKey(c)) {
if (!stack.isEmpty() && map.get(c) == stack.peek()) {
stack.pop();
} else {
return 0;
}
} else {
stack.push(c);
}
}
return stack.isEmpty() ? 1 : 0;
}
100% Java
public int solution(String S) {
Stack<Character> stack = new Stack<>();
for(int i=0; i<S.length(); i++) {
char c = S.charAt(i);
if (c == '[' || c == '{' || c == '(' || c == 'V') {
stack.push(c);
} else if (c == ']' || c == '}' || c == ')' || c == 'W') {
if (checkBracket(stack, c)) {
stack.pop();
} else {
return 0;
}
} else {
return 0;
}
}
if (stack.empty()) {
return 1;
}
return 0;
}
private boolean checkBracket(Stack<Character> stack, char bracket) {
if (stack.empty()) return false;
char lastStackBracket = stack.peek();
if (lastStackBracket == '{' && bracket == '}') {
return true;
} else if (lastStackBracket == '[' && bracket == ']') {
return true;
} else if (lastStackBracket == '(' && bracket == ')') {
return true;
} else if (lastStackBracket == 'V' && bracket == 'W') {
return true;
}
return false;
}
当然需要导入java.util:
import java.util.*;
function solution(S) {
if (0 === S.length) {
return 1
}
let stack = []
for (let i = 0; i < S.length; i++) {
if ('(' === S[i] || '{' === S[i] || '[' === S[i]) {
stack.push(S[i])
} else {
let couple = [stack.pop(), S[i]].join('')
if ('()' !== couple && '{}' !== couple && '[]' !== couple) {
return 0
}
}
}
if (stack.length) {
return 0
}
return 1
}
我在 Swift 中的解决方案。应该可以正常工作
public func Brackets(_ S : inout String) -> Int {
var Stack = [Character]()
let matching : [Character:Character] = ["(":")", "[":"]", "{":"}"]
for s in S {
let char = S.removeFirst()
if "({[".contains(char) {
print(char)
Stack.append(char)
}
if( "]})".contains(char)) {
print(char)
let bracket = Stack.removeLast()
if matching[bracket] != char {
return 0
}
}
}
return 1
}
var S1 = "{[()()]}"
var S2 = "([)()]"
print("Brackets: ", Brackets(&S1))
print("Brackets: ", Brackets(&S2))
简单java解决方案，100/100
public int solution(String S) {
Deque<Character> stack = new ArrayDeque<Character>();
for(int i = 0; i < S.length(); i++) {
char c = S.charAt(i);
switch (c) {
case ')':
if (stack.isEmpty() || stack.pop() != '(')
return 0;
break;
case ']':
if (stack.isEmpty() || stack.pop() != '[')
return 0;
break;
case '}':
if(stack.isEmpty() || stack.pop() != '{')
return 0;
break;
default:
stack.push(c);
break;
}
}
return stack.isEmpty() ? 1 : 0;
}
我知道这与您的问题没有直接关系。
但是我有一个有效的解决方案，运行 时间复杂度为 O(N)，space 复杂度为 O(1)。 该解决方案在 codility 中获得 100/100。
用 C++ 编写：
int solution(string S) {
int N = S.size();
if(N == 0) return 1;//empty string is properly nested
if(S[0] == ')' || S[0] == ']' || S[0] == '}' ) return 0;// a properly nested string cannot beging with those chars
if(S[N-1] == '(' || S[N-1] == '[' || S[N-1] == '{' ) return 0; // cannot end with those chars
int paren_open = 0;
int brac_open = 0;
int curl_open = 0;
for(int i =0 ; i < N;++i){
if(S[i] == ')' && (paren_open == 0 || S[i-1] == '[' || S[i-1] == '{')) return 0; //expected opening but got closing
if(S[i] == ']' && (brac_open == 0 || S[i-1] == '(' || S[i-1] == '{')) return 0; //same here
if(S[i] == '}' && (curl_open == 0 || S[i-1] == '[' || S[i-1] == '(')) return 0; //same here
if(S[i] == '(') paren_open++;
else if(S[i] == ')') paren_open--;
else if(S[i] == '[') brac_open++;
else if(S[i] == ']') brac_open--;
else if(S[i] == '{') curl_open++;
else if(S[i] == '}') curl_open--;
}
if(paren_open == 0 && brac_open == 0 && curl_open ==0)
return 1;
return 0; }
找不到任何 python 脚本...但它就在这里！尽量保持简单。
def solution(S):
# write your code in Python 3.6
arr = []
if len(S) < 1:
return 1
if not isinstance(S, str):
return 0
for i in range(0, len(S)):
# print(S[i])
if startSym(S[i]):
arr.append(value(S[i]))
# print(arr)
elif endSym(S[i]):
if len(arr) > 0 and value(S[i]) == arr[len(arr) - 1]:
# print(S[i])
# print(arr)
del arr[len(arr) - 1]
else:
return 0
else:
return 0
if len(arr) == 0:
return 1
else:
return 0
def startSym(x):
if x == '{' or x == '[' or x == '(':
return True
else:
return False
def endSym(x):
if x == '}' or x == ']' or x == ')':
return True
else:
return False
def value(x):
if x == '{' or x == '}':
return 1
if x == '[' or x == ']':
return 2
if x == '(' or x == ')':
return 3
此问题的简洁明了 Python 解决方案。 Codility 100%
def solution(S):
matches, stack = dict(['()', '[]', '{}']), []
for i in S:
if i in matches.values():
if stack and matches[stack[-1]] == i:
stack.pop()
else:
return 0
else:
stack.append(i)
return int(not stack)
Ruby 100%
def solution(s)
s.split('').inject([]) do |stack, el|
next stack.push(el) if ['[', '{', '('].include?(el)
current = stack.pop
next stack if (current == '{' && el == '}') ||
(current == '(' && el == ')') ||
(current == '[' && el == ']')
return 0
end.empty? ? 1 : 0
end
这是 python 中的解决方案，在 Codility
处为 100%我添加了一些解释和步骤，希望这对任何人有帮助...
Idea Idea is to use stack concept Used array [] as stack Keep adding item in stack until open brackets found, Keep popping up item if closing bracket found. On each pop of item check popped item it should match with the opposite bracket as explained in example else not balanced.
Operation
4 push 4 pop
{[()()]}
push {
push [
push (
pop )
push (
pop )
pop ]
pop }
gets empty
2 push 1 pop
([)()]
(
[
) - not matching with [ so not balanced
代码-
def solution(S):
stack = []
for bracket in S:
# open bracket found push in to stack, used array as stack append item at top
if bracket == "{" or bracket == "[" or bracket == "(":
stack.append(bracket)
# any closing bracket found and stack is not empty remote item from stack top
elif bracket == "}" and stack:
pop_item = stack.pop()
# check popped item, if it is not similar( ie. opposite or open) as bracket then this S can not be balanced
if pop_item != "{":
return 0
elif bracket == "]" and stack:
pop_item = stack.pop()
if pop_item != "[":
return 0
elif bracket == ")" and stack:
pop_item = stack.pop()
if pop_item != "(":
return 0
# at any point if neither open nor close operation can be performed, stack is not balanced
else:
return 0
print(stack)
# if stack is empty stack, it is balanced ie. all push and pop operation on S is successful¬.
if not stack:
return 1
# S is not balanced
return 0
if __name__ == '__main__':
# result = solution("{[()()]}")
result = solution("([)()]")
print("")
print("Solution " + str(result))
运行 测试用例 -
['{']
['{', '[']
['{', '[', '(']
['{', '[']
['{', '[', '(']
['{', '[']
['{']
[]
Solution 1
['(']
['(', '[']
Solution 0
这里是Java100%
public int solution(String S) {
// write your code in Java SE 8
List open = Arrays.asList('(', '{', '[');
List close = Arrays.asList(')', '}', ']');
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < S.length(); i++) {
if (open.contains(S.charAt(i))) {
stack.push(S.charAt(i));
} else if (close.contains(S.charAt(i)) && !stack.isEmpty()) {
Character top = stack.peek();
if (open.indexOf(top) == close.indexOf(S.charAt(i))) {
stack.pop();
} else {
return 0;
}
} else {
return 0;
}
}
return stack.isEmpty() ? 1 : 0;
}
我在 C# 中的 100% 解决方案。
using System;
using System.Collections.Generic;
using System.Linq;
class Solution {
private Dictionary<char,char> closing = new Dictionary<char,char>{{'}','{'},{')','('},{']','['}};
public int solution(string S) {
var stack = new Stack<char>();
foreach(var c in S)
{
if(!closing.Keys.Contains(c))
stack.Push(c);
else if(!stack.Any() || closing[c] != stack.Pop() )
return 0;
}
return !stack.Any() ? 1 : 0;
}
}
def solution(S):
if len(S) == 0:
return 1
opening = ["(", "{", "["]
closing = [")", "}", "]"]
ls_my_o = []
for s in S:
if s in opening:
ls_my_o.append(s)
elif s in closing:
if len(ls_my_o) < 1:
return 0
ele = ls_my_o.pop()
if opening.index(ele) != closing.index(s):
return 0
if len(ls_my_o) == 0:
return 1
return 0
Javascript 100% 解决方案
function solution(S) {
const stack = []
const obj = { ")": "(", "}": "{", "]": "[" }
for (i = 0; i < S.length; i++) {
if (S[i] === '(' || S[i] === '{' || S[i] === '[') {
stack.push(S[i])
} else {
const last = stack.pop()
if (obj[S[i]] !== last) return 0
}
}
return stack.length === 0 ? 1 : 0
}
这是一个简单的 Python 解决方案 (100%)：
# Brackets
def solution(S):
if not S:
return 1
stack = []
brackets = {"(": ")", "{": "}", "[": "]"}
for elem in S:
if elem in brackets:
stack.append(elem)
if elem in brackets.values():
if stack:
if elem == brackets[stack.pop()]:
continue
else:
return 0
else:
return 0
return 0 if stack else 1
Swift 5 (100%)
public func solution(_ S : inout String) -> Int {
var stack: [Character] = []
let pairFor: [Character: Character] = ["(":")",
"{":"}",
"[":"]"]
let opening: Set<Character> = ["(","{","["]
let closing: Set<Character> = [")","}","]"]
for char in S {
if opening.contains(char) {
stack.append(char)
} else if closing.contains(char) {
guard stack.isEmpty == false else {
return 0
}
let bracket = stack.removeLast()
if pairFor[bracket] != char {
return 0
}
}
}
return stack.isEmpty ? 1 : 0
}
PHP 准确率为 100% 的解决方案
$sa = str_split($S);
if(strlen($S) == 0){
return 1;
}
$count = count($sa);
$res =1;
$opening = ['{'=>'}','('=>')','['=>']'];
$array =['{'=>'}','}'=>'{',')'=>'(','('=>')','['=>']',']'=>'['] ;
$stack = [];
for($i =0;$i<$count;$i++){
if(isset($opening[$sa[$i]])){
array_push($stack,$sa[$i]);
}else{
if(count($stack) == 0){
return 0;
}
$v = array_pop($stack);
if($array[$sa[$i]] !== $v){
return 0;
}
}
}
if (sizeof($stack) != 0) return 0;
return 1;
C++ (100%)
#include <stack>
int solution(string &S) {
// write your code in C++14 (g++ 6.2.0)
auto N = S.size();
stack<char> ST;
for(decltype(N) i{0}; i < N; i++) {
if ((S[i] == '{') || (S[i] == '[') || (S[i] == '(')) {
ST.push(S[i]);
}
else {
if (ST.empty()) {
return false;
}
char top = ST.top();
ST.pop();
if ((S[i] == ')') && (top != '(')) {
return false;
}
if ((S[i] == ']') && (top != '[')) {
return false;
}
if ((S[i] == '}') && (top != '{')) {
return false;
}
}
}
return ST.empty();
}
class Solution {
public int solution(String S) {
// write your code in Java SE 8
Stack<Character> myStack = new Stack<Character>();
for(Character singleChar : S.toCharArray()){
if((singleChar.equals('(')) || (singleChar.equals('{')) || (singleChar.equals('['))){
myStack.push(singleChar);
}
else{
if(myStack.size() == 0){
System.out.println("Stack size");
return 0;
}
if(singleChar.equals(')')){
if(myStack.peek().equals('('))
myStack.pop();
else
return 0;
}
if(singleChar.equals('}')){
if(myStack.peek().equals('{'))
myStack.pop();
else
return 0;
}
if(singleChar.equals(']')){
if(myStack.peek().equals('['))
myStack.pop();
else
return 0;
}
}
}
if(myStack.size()==0)
return 1;
else
return 0;
}
}
我认为这是一个更具可读性的 Java 解决方案，得分为 100%：
https://app.codility.com/demo/results/trainingUY545E-2EQ/
import java.util.Stack;
public class Brackets {
public int solution(String S) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < S.length(); i++) {
if (!process(stack, S.charAt(i))) {
return 0;
}
}
return stack.empty() ? 1 : 0;
}
private boolean process(Stack<Character> stack, char ch) {
Character opener = getOpener(ch);
if (opener == null) {
stack.push(ch);
} else {
if (stack.empty()) {
return false;
}
char top = stack.peek();
if (opener.equals(top)) {
stack.pop();
} else {
return false;
}
}
return true;
}
private Character getOpener(char ch) {
switch (ch) {
case ')':
return '(';
case '}':
return '{';
case ']':
return '[';
default:
return null;
}
}
}
我的 %100 JAVA 解决方案
class Solution {
public int solution(String S) {
Stack<Character> myStack = new Stack<>();
char[] chars = S.toCharArray();
for (int i = 0; i < chars.length; i++) {
char coming = chars[i];
switch(coming){
case '(': case '{': case '[':
myStack.push(coming);
break;
case ')': case '}': case ']':
if(myStack.isEmpty())
return 0;
char popped = myStack.pop();
if(!isValidPair(coming, popped))
return 0;
}
}
if(!myStack.isEmpty())
return 0;
return 1;
}
private boolean isValidPair(char c, char s) {
return ((c == ')' && s == '(') || (c == '}' && s == '{') || (c == ']' && s == '['));
}
}
我的 100% JavaScript 时间复杂度为 O(N) 的解决方案：
function solution(S) {
const openingTags = {
'[': ']',
'{': '}',
'(': ')',
};
const stack = [];
for (const char of S) {
// if char is not an opening tag, it is a closing tag
if (openingTags.hasOwnProperty(char)) {
stack.push(char);
} else if (openingTags[stack.pop()] !== char) {
return 0;
}
}
return Number(stack.length < 1);
}