Java Codility : Brackets 确定给定的括号字符串是否正确嵌套

Codility : Brackets Determine whether a given string of parentheses is properly nested

提问by klind

Problem description from codility :

来自 codility 的问题描述：

A string S consisting of N characters is considered to be properly nested if any of the following conditions is true:

如果满足以下任一条件，则由 N 个字符组成的字符串 S 被认为是正确嵌套的：

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. For example, the string "{[()()]}" is properly nested but "([)()]" is not.

S 为空；S 的形式为 "(U)" 或 "[U]" 或 "{U}"，其中 U 是正确嵌套的字符串；S 的形式为“VW”，其中 V 和 W 是正确嵌套的字符串。例如，字符串 "{[()()]}" 被正确嵌套，但 "([)()]" 不是。

Write a function:

写一个函数：

class Solution { public int solution(String S); }

类解决方案 { 公共 int 解决方案（字符串 S）；}

that, given a string S consisting of N characters, returns 1 if S is properly nested and 0 otherwise.

给定一个由 N 个字符组成的字符串 S，如果 S 正确嵌套，则返回 1，否则返回 0。

For example, given S = "{[()()]}", the function should return 1 and given S = "([)()]", the function should return 0, as explained above.

例如，给定 S = "{[()()]}"，函数应该返回 1，给定 S = "([)()]"，函数应该返回 0，如上所述。

Assume that:

假使，假设：

N is an integer within the range [0..200,000]; string S consists only of the following characters: "(", "{", "[", "]", "}" and/or ")". Complexity:

N是[0..200,000]范围内的整数；字符串 S 仅包含以下字符：“(”、“{”、“[”、“]”、“}”和/或“)”。复杂：

expected worst-case time complexity is O(N); expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

预期的最坏情况时间复杂度为 O(N)；预期的最坏情况空间复杂度为 O(N)（不计算输入参数所需的存储空间）。

I get 87% I cant seem to figure out the problem.

我得到 87% 我似乎无法找出问题所在。

Here is my code :

这是我的代码：

   // 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;

    }
}

采纳答案by Leeor

Your first condition in the closing brackets block checks whether your stack has the size != 1. I assume this is meant to check that you don't have any leftover opening brackets, which is a good idea. However, you'll miss this entire check if your last char isn't a closing bracket/paren/..

您在右括号块中的第一个条件检查您的堆栈是否具有大小 != 1。我认为这是为了检查您没有任何剩余的左括号，这是一个好主意。但是，如果您的最后一个字符不是右括号/paren/..，您将错过整个检查。

This for example would fail for an input like (((.

例如，对于像(((.

A simple fix would be replacing this condition with a check afterthe loop ends that the stack is indeed empty.

一个简单的解决方法是在循环结束后检查堆栈确实为空来替换此条件。

回答by Morgen

Your best bet with these sort of errors is to sit down and writes some unit tests (JUnit is a good framework) to verify your understanding of how the algorithm works.

解决此类错误的最佳选择是坐下来编写一些单元测试（JUnit 是一个很好的框架），以验证您对算法如何工作的理解。

In this case, as Trengothas figured out that the "negative_match" input is ))((, you'll want at least these test cases:

在这种情况下，由于Trengot已经发现“negative_match”输入是))((，您至少需要这些测试用例：

• ))((: This is your base test, once this is passing you're fulfilling the requirements, and can declare at least partial victory.
• }}{{: Is this a general error, or only related to mishandling a particular character?
• })({: Is it related to the repeated character, or does it show up in mixed input as well?
• (}{): Is this an edge-case related to having an opening token at the start of the string, or does this behavior show up more generally?

• ))((：这是您的基本测试，一旦通过，您就满足了要求，并且可以宣布至少部分胜利。
• }}{{: 这是一个普遍的错误，还是只与错误处理特定字符有关？
• })({: 是否与重复字符有关，还是在混合输入中也会出现？
• (}{)：这是与在字符串开头有一个打开标记有关的边缘情况，还是这种行为更普遍地出现？

Once you understand what it is actuallydoing, instead of what your brain tells you it is doing (and your brain willlie to you about this), fixing it should be fairly straightforward.

一旦你了解它实际在做什么，而不是你的大脑告诉你它在做什么（你的大脑会在这方面对你撒谎），修复它应该是相当简单的。

回答by klind

So after Leeor suggestions here is a 100% solution

所以在 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;

    }
}

回答by David Yachnis

Code: 06:12:11 UTC, c, final, score: 100.00

代码：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;
    }

回答by Jung Oh

100% simple JavaScript solution

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;
}

回答by moxi

Here's a Java 100/100:

这是一个 Java 100/100：

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. Hope it helps.

这是代码的链接。希望能帮助到你。

回答by Kundan Kumar

Passed codility test 100/100 in java.

在 Java 中通过了 codility 测试 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);
        }
}

回答by Caesar Avgvstvs

here you have my 100% solution in java: https://codility.com/demo/results/training2C7U2E-XM3/

在这里你有我的 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;
}

回答by Vertigo cache

This is my C# simple solution which got 100% for Correctness and 100% Performance. Time Complexity is O(N). https://codility.com/demo/results/trainingRVS3SF-DC6/

这是我的 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;
    }
}

回答by krishna

I got 100% with the following solution in java. The time complexity is O(N)

我在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;
}

}

}