Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
231 views
in Technique[技术] by (71.8m points)

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

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
See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...