Interview Coding Exercise – Nested String (Python)

stack-data-structure

Nested String

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: def solution(S) ,that, given a string S consisting of N characters, the function returns 1 if S is properly nested and 0 otherwise.

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

The assumptions are:

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

Complexity requirements:

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

Solution (Python)

Stack is a FILO (First In Last Out) data structure. The idea is push a opening tag to the stack and pop one from and check if it matches when we see the closing tag. The only thing you need to pay attention to is to check if the stack is empty when you want to pop an element from the stack.

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
27
28
29
30
31
32
33
34
35

def IsNested(s):
    stack = []
    for x in s:
        if x in ['(', '{', '[']:
            stack.append(x)
        elif x in [')', '}', ']']:
            if len(stack) == 0:
                return 0
            # Pop an element to see if matches
            y = stack.pop()
            if x == ')' and y != '(':
                return 0
            elif x == ']' and y != '[':
                return 0
            elif x == '}' and y != '{':
                return 0
    return 1     
    
if __name__ == '__main__':
    # Define Test Cases
    testcases = {
        "([)()]": 0,
        "{[()()]}": 1,
        "": 1,
        "{}": 1,
        "[]()": 1,
        ")(": 0,
        "}{()": 0,
        "()[}": 0      
    }
    
    for test in testcases.keys():
        assert testcases[test] == IsNested(test), "Test " + test + " Failed"
    
    print ("All OK.")

def IsNested(s):
    stack = []
    for x in s:
        if x in ['(', '{', '[']:
            stack.append(x)
        elif x in [')', '}', ']']:
            if len(stack) == 0:
                return 0
            # Pop an element to see if matches
            y = stack.pop()
            if x == ')' and y != '(':
                return 0
            elif x == ']' and y != '[':
                return 0
            elif x == '}' and y != '{':
                return 0
    return 1     
    
if __name__ == '__main__':
    # Define Test Cases
    testcases = {
        "([)()]": 0,
        "{[()()]}": 1,
        "": 1,
        "{}": 1,
        "[]()": 1,
        ")(": 0,
        "}{()": 0,
        "()[}": 0      
    }
    
    for test in testcases.keys():
        assert testcases[test] == IsNested(test), "Test " + test + " Failed"
    
    print ("All OK.")

Support me and my work as a witness by

• voting me here, or
• voting me as a proxy.

Thank you! Some of My Contributions: SteemIt Tutorials, Robots, Tools and APIs

–EOF (The Ultimate Computing & Technology Blog) —