0
votes

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
1
Your solution of scanning the first and last character of a section won't work for your first case {[()()]}, since at the end you'll be looking at the characters in the middle )(. - Colonel Thirty Two
Hint: Since the definition of proper nesting is recursive, it's usually simplest to implement the tester with recursion as well. - Barmar
Since your algorithm seems to work with your test strings you need to make up some more complicated test strings, both correctly nested ones and incorrectly nested ones. Then manually "walk through" your algorithm with those strings (i.e. do it by hand, on paper) and see what happens. Now do the same thing using dognose's algorithm. In my experience, working through an algorithm manually can often help me understand how to turn it into code. - PM 2Ring

1 Answers

2
votes

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