Codility : Nesting

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:

def solution(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).

 

 

PYTHON SOLUTION

def solution(S):
    # write your code in Python 2.7
    if not S:
        return 1
    if len(S) ==1:
        return 0 
    if S[0] ==")":
        return 0
    
    opens=[]
    n=len(S)
    for i in range(0,n):
        if S[i] =="(":
            opens.append(S[i])
        elif   S[i] ==")":
            if len(opens) ==0:
                return 0
            elif "(" != opens.pop():
                return 0
            
    if len(opens) ==0:
        return 1

    return 0            
            

 

email@djangotutsme.com April 21, 2016, 9:03 a.m.