Determine whether a given string of parentheses (multiple types) is properly nested.

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

  • 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.

Write a function:

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

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

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

Write an efficient algorithm for the following assumptions:

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

class Solution {
    public int solution(String S) {
         if (S.isEmpty()) {
            return 1;
        }
        char[] sArr = S.toCharArray();
        int isOk = 0;
        Stack<Integer> stack = new Stack<>();
        Map<Integer, Character> symbolMap = new HashMap<Integer, Character>() {{
            put(0, '}');
            put(1, ']');
            put(2, ')');
            put(3, '{');
            put(4, '[');
            put(5, '(');
        }};

        for (char c : sArr) {
            int symbolType = findSymbol(c);
            if (symbolType != -1) {
                switch (symbolType) {
                    case 0:
                    case 1:
                    case 2:
                        stack.push(symbolType);
                        break;
                    case 3:
                    case 4:
                    case 5:
                        if (!stack.empty()) {
                            if (symbolMap.get(stack.pop()) == c) {
                                isOk = 1;
                            } else {
                                return 0;
                            }
                        } else {
                            return 0;
                        }
                }

            }
        }
        if (!stack.empty()){
            return 0;
        }
        return isOk;
    }
    private static int findSymbol(char s) {
        switch (s) {
            case '{':
                return 0;
            case '[':
                return 1;
            case '(':
                return 2;
            case '}':
                return 3;
            case ']':
                return 4;
            case ')':
                return 5;
            default:
                return -1;
        }
    }
}

我一開始的做法是先找左刮號之後就用indexOf()和lastIndexOf()找右刮號，如果數字相同就表示刮號正確，否則就取子字串結尾從lastIndexOf()找出的數字，然後再判斷刮號內是否包含不正確的刮號。

然後就發現這樣做很不正確，因為只要是兩個正常刮號就會有問題，如()()，所以就改成取左刮號先放到堆疊中，直到碰到右刮號再從堆疊取出做比對，做法比上一步容易多了，真不知一開始在想什麼，我找符號的方式是將符號轉成數字再從一個map中比對，不過應該是可以改寫用一個容器就可以。

優化過方法，直接存符號不用數字再轉了。

/**
     * Brackets:
     * Determine whether a given string of parentheses (multiple types) is properly nested.
     * 0:err 1:ok
     */
    private static int brackets(String s) {
        if (s.isEmpty()) {
            return 1;
        }
        char[] sArr = s.toCharArray();
        int isOk = 0;
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> symbolMap = new HashMap<Character, Character>() {{
            put('{', '}');
            put('[', ']');
            put('(', ')');
        }};
        for (char c : sArr) {
            switch (c) {
                case '{':
                case '[':
                case '(':
                    stack.push(c);
                    break;
                case '}':
                case ']':
                case ')':
                    if (!stack.empty()) {
                        if (symbolMap.get(stack.pop()) == c) {
                            isOk = 1;
                        } else {
                            return 0;
                        }
                    } else {
                        return 0;
                    }
            }
        }
        if (!stack.empty()) {
            return 0;
        }
        return isOk;
    }