python - Why does this solution fail? Nested and matching brackets

Question

I am still failing tests for

• "negative_match: invalid structures,";
• "simple_grouped: simple grouped positive and negative test, length=22";
• "large1 simple large positive test, 100K ('s followed by 100K )'s + )("; and
• "large2 simple large negative test, 10K+1 ('s followed by 10K )'s + )( + ()".

Can anyone see what my error is? The code I wrote works for all strings I tested...

Here is a description of the task:

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

Assume that:

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

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

Here is my solution:

def solution(S):
# write your code in Python 2.7
if S == "":
    return 1
length = len(S)
start = 0
end = length-1

if length%2 != 0:
    return 0

for i in range(0, length):
    if (S[start] == '(') and (S[end] != ')'):
        return 0
    if (S[start] == '[') and (S[end] != ']'):
        return 0
    if (S[start] == '{') and (S[end] != '}'):
        return 0
    start = start +1
    end = end -1

return 1    

pass

Answer 1

You are seeking from left to right and right to left - this will fail on ([]{}) - even if its valid, cause you would compare [ with }. (start = 1 and end = 4)

---

As a verbal description I would do the following:

• Create a second string of expected values. (Explain this later)
• Iterate over the given string to build up your expectation string, when you find a opening bracket - compare, whenever you find a closing bracket.

Example: The given String is {([])].

for i in range(0, length):

• IF opening bracket [, {, ( put the expected closing bracket to the end of the expectation-string. i.e. ],} or )
• ELSE (:= if closing bracket):
  • closing bracket matches LAST CHARACTER in the expactation-string? -> remove from expectation-string, proceed.
  • closing bracket not matches LAST CHARACTER in the expectation-string? -> invalid format
  • expectation-string empty? -> invalid format
  • Input-String end reached, expectation-string NOT empty? -> invalid format.

That would process the given string like this:

i  | found value  | e-string before| e-string after | remark
0  | {            |                | }              | added }
1  | (            | }              | })             | added ) 
2  | [            | })             | })]            | added ]
3  | ]            | })]            | })             | last element was ] -> removed
4  | )            | })             | }              | last element was ) -> removed
5  | ]            | }              | }              | found ] but expected } -> invalid.

---

Edit: Since the expected "Storage complexity" is Oh(n) as well (not counting input arguments) you will run into a storage complexity of Oh(n) EXACTLY then, when the given string has n opening brackets - no problem. But you ofc. should use a second string then, cause lists have overhead.

For the runtime complexity:

• Setting a value at a certain string position is atomic -> Oh(1) (meaning constant)
• if() statements are atomic -> Oh(1) (meaning constant)
• Removing characters is atomic -> Oh(1) (meaning constant)
• Your for loop has Oh(n)(depending on n)

Sum it up, you'll get Oh(n).

---

If you like to implement this in Python, you can use http://dog-net.org/string.php to validate your "steps". :-)

---

ps.: I'm not providing a copy&paste solution on purpose! :P