Codility---Nesting

Task description

A string S consisting of N characters is called properly nested if:

S is empty;

S has the form "(U)" where U is a properly nested string;

S has the form "VW" where V and W are properly nested strings.

For example, string "(()(())())" is properly nested but string "())" isn't.

Write a function:

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

that, given a string S consisting of N characters, returns 1 if string 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.

Assume that:

N is an integer within the range [0..1,000,000];

string S consists only of the characters "(" and/or ")".

Complexity:

expected worst-case time complexity is O(N);

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

Solution

Programming language used: Java

Total time used: 23 minutes

Effective time used: 23 minutes

Code: 15:25:23 UTC, java, final, score: 100

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

// you can also use imports, for example:

// import java.util.*;

// you can write to stdout for debugging purposes, e.g.

// System.out.println("this is a debug message");

import java.util.Stack;

class Solution {

    public int solution(String S) {

        // write your code in Java SE 8

        Stack<Character> st = new Stack<Character>();

        if(S == null)

            return 1;

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

            if(S.charAt(i) == '(')

                st.push('(');

            else if(S.charAt(i) == ')' && !st.empty())

                st.pop();

            else if(S.charAt(i) == ')' && st.empty())

                return 0;

        }

        if(st.empty())

            return 1;

        else

            return 0;

    }

}

https://codility.com/demo/results/trainingUYAFS5-NWU/

巴特西

Codility---Nesting

最新文章

热门文章