檢查括號嵌套在一個字符串中

Question

我對Codility進行了一次培訓挑戰，檢查字符串中括號的嵌套。要檢查的括號是{,},(,),[,]。我寫了下面的通過O（n）時間和空間的Java程序，但我有一種感覺，我可以減少額外的空間。此外，我認爲必須有一個可以更高效地處理這種情況的數據結構。使用ArrayList而不是數組可能會有所幫助。我需要的是批評我的代碼。提前致謝。

這裏是我寫的代碼：

import java.util.HashMap; 
class Solution { 
    public int solution(String S) { 
     char[] stack = new char[S.length()]; 
     int last = -1; 
     HashMap hm = new HashMap(); 
     hm.put('}', '{'); 
     hm.put(')', '('); 
     hm.put(']', '['); 
     for(int i=0; i<S.length(); i++){ 
      char next = S.charAt(i); 
      if(next == '}' || next == '{' || next == ')' || next == '(' || 
      next == ']' || next == '[') 
      { 
       if(last!=-1 && hm.containsKey(next) && stack[last] == hm.get(next)){ 
        last--; 
       } 
       else{ 
        last++; 
        stack[last] = S.charAt(i); 
       } 
      } 
     } 
     if(last == -1){ 
      return 1; 
     } 
     return 0; 
    } 
} 

Answer 1

這裏是一個列表的解決方案：

import java.util.LinkedList;  

class Solution { 

    public int solution(String S) { 
     LinkedList<Character> stack = new LinkedList<>(); 

     for (int i = 0; i < S.length(); i++) { 
      char c = S.charAt(i); 

      if (c == '{' || c == '[' || c == '(') { 
       stack.push(c); 
      } else { 
       if (stack.isEmpty()) { 
        return 0; 
       } 

       char preceding = stack.pop(); 

       if (c == ')' && preceding != '(') { 
        return 0; 
       } 

       if (c == ']' && preceding != '[') { 
        return 0; 
       } 

       if (c == '}' && preceding != '{') { 
        return 0; 
       } 

      } 
     } 

     return stack.isEmpty() ? 1 : 0; 
    } 
} 

Answer 2

的JavaScript sulution爲codility支架

function solution(S) { 
    var head = 0, 
     stack = [], 
     s_ln = S.length; 
     d = { 
      "(" : ")", 
      "{" : "}", 
      "[" : "]" 
     }; 

    for(var i = 0; i < s_ln; i++) { 
     if(d[S[i]]) { 

      stack[head++] = S[i]; 

     } else { 
      if(d[stack[head-1]] === S[i]) { 
       head--; 
      } else { 
       return 0;  
      } 
     } 

     if (head < 0) return 0; 

    } 

    return head === 0 ? 1 : 0; 
} 

result 100% 100%

Answer 3

的Java 100/100

https://codility.com/demo/results/demo97TPVG-CPP/

我包括堆棧的定義，這就是爲什麼一點點的時間，但解決方法很簡單：

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

Answer 4

不是Java，JavaScript的，但是，它仍然可以給予一些靈感

function checkBrackets(str) { 
    var brackets = { '(': ')', '{': '}', '[': ']' }; 
    var container = { ')': 1, '}': 1, ']': 1 }; 
    var passed = true; 

    for (var i = 0, len = str.length; i < len; i++) { 
    if (brackets[str[i]]) { 
     var match = brackets[str[i]]; 
     container[match] = container[match] ? container[match]+1 : 1; 
    } else if (container[str[i]]) { 
     container[str[i]]--; 
    } 
    } 

    for (var br in container) { 
    if (container[br] !== 1) { return false; } 
    } 

    return passed; 
} 

console.log(checkBrackets('(])')); 
console.log(checkBrackets('()')); 
console.log(checkBrackets('(()')); 
console.log(checkBrackets('({[]})')); 

Answer 5

我會在2016年嘗試回答這個問題。:-p。 下面的代碼通過100/100並且很容易理解。

package codility.com; 
 

 
import java.util.Stack; 
 

 
/** 
 
* Created by rattanak on 6/29/2016. 
 
*/ 
 
public class Solution_Stack_Queue { 
 
    public static void main(String[] args) { 
 
     String s = "()()"; 
 
     System.out.print(perfectNesting(s)); 
 
    } 
 

 
    //Q: https://codility.com/c/run/trainingB4J4DF-UZU 
 
    // S empty : return 1; 
 
    // (()(())()) return 1 
 
    // (() : return 0 
 
    // Use of stack to save chars 
 
    public static int perfectNesting(String s) { 
 

 
     if (s.length() == 0) return 1; 
 
     if (s.length() % 2 == 1) return 0; //odd 
 
     Stack<Character> st = new Stack<Character>(); 
 
     for (int i =0; i < s.length(); i++){ 
 
      char ch = (char)s.charAt(i); 
 
      if (ch == '(' || ch == '{' || ch == '['){ 
 
       st.push(s.charAt(i)); 
 
      } else { //found) 
 
       if (st.isEmpty()) return 0; 
 
       if (st.peek() != '('){ 
 
        return 0; 
 
       } else { 
 
        //remove 
 
        st.pop(); 
 
       } 
 
      } 
 
     } 
 

 
     if (st.isEmpty()) return 1; 
 

 
     return 0; 
 
    } 
 
}

結果：https://codility.com/demo/results/training8XUE3W-JTX/

讓我知道在下面的評論，如果您有任何問題。

Answer 6

這裏是我的JavaScript的解決方案，對codility也在正確性和性能得分100/100：

https://codility.com/demo/results/trainingXB4S2W-D3F/

function solution(text) { 
    var openBrackets = ['(', '[', '<', '{']; 
    var closedBrackets = [')',']','>','}']; 
    var requiredClosedBrackets = []; 
    var chars = text.split(''); 
    var result = true; 
    for (var i = 0; i < chars.length; i++) { 
     for (var j = 0; j < openBrackets.length; j++) { 
     if (chars[i] == openBrackets[j]) { 
      requiredClosedBrackets.push(closedBrackets[j]); 
     } else if (chars[i] == closedBrackets[j]) { 
      if (chars[i] != requiredClosedBrackets[requiredClosedBrackets.length - 1]) { 
      return 0; 
      } else { 
      requiredClosedBrackets.pop(); 
      } 
     } 
     } 
    } 

    return (requiredClosedBrackets.length == 0) ? 1 : 0; 
}