[Codility] 第七課 Brackets

簡而言之，這題目就是要判斷 S 字串是否有對稱的括號，就返回 1。
利用 Stack 後進先出的方式來一一判別對稱則 pop 出來，最後是空的就是對稱了。

題目

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 ")".

Java 程式碼

// you can also use imports, for example:
import java.util.*;
 
class Solution {
    public int solution(String S) {
        // write your code in Java SE 8
        if(S.length() == 0)
            return 1;
            
        if(S.length() > 200000)
            return 0;
        
        Stack st = new Stack();
        for(int i=0; i< S.length();i++){
            char ch = S.charAt(i);
            if(ch == '{' || ch == '(' || ch == '['){
                st.push(S.charAt(i));
            }else{
                
                if(st.empty()){
                    return 0;
                }
                char stPeek =(char) st.peek();
                if(ch == '}' && stPeek == '{'){
                    st.pop();
                }
                 if(ch == ']' && stPeek == '['){
                    st.pop();
                } 
                if(ch == ')' && stPeek == '('){
                    st.pop();
                }
                
                
            }
        }
        
        if(st.empty()){
            return 1;
        }else{
            return 0;
        }
    }
}

分數共拿 100%
任何問題歡迎交流討論，一起學習！

更多面試相關

⇒ [Codility] 面試寫題目經驗感想



感謝相關連結
https://www.codility.com/
https://app.codility.com/programmers/lessons/7-stacks_and_queues/brackets/