您是从的左至右和右键寻求左的 - 这将失败（[] {}） - 即便其有效的，因为你会比较 [与} 。 （启动= 1 和结束= 4 ）

---

作为一个口语化的描述我会做到以下几点：

• 创建预期值的第二个字符串。 （解释一下这个版本）
• 迭代指定字符串来建立你的期望的字符串，当你发现一个左括号 - 相比，无论何时你发现一个右括号

例如：给定的字符串是 {（[]）]

 为我的range（0，长度）：
 

• 如果左括号 [， {，（把预期的右括号的期望字符串的结尾。即] ，} 或）
• ELSE（：=如果右括号）：
  • 的右括号的匹配在expactation串最后一个字符？ - >从期望字符串删除，请
  • 的右括号的不匹配，期望字符串最后一个字符？ - >无效的格式
  • 期望字符串是空的？ - >无效的格式
  • 输入字符串年底达到预期字符串不是空的？ - >无效的格式

这将处理指定的字符串是这样的：

  I |发现价值|电子字符串之前|电子字符串后面|备注
0 | {| | } |添加 }
1 | （|} |}）|添加 ）
2 | [| }）| }）] |添加 ]
3 | ] | }）] | }）|最后一个因素是 - ＆GT;移除
4 | ）| }）| } |最后一个元素是） - ＆GT;移除
5 | ] | } | } |发现]，但预计}  - ＆GT;无效。
 

---

编辑：由于预期的存储的复杂性是呵呵（N）以及（不包括输入参数），你会碰到一个存储的复杂性呵呵（N） EXACTLY那么，当给定的字符串有 N 开括号 - 没问题。但是你OFC。应使用第二个字符串那么，导致列表有开销。

有关运行的复杂性：

• 设置在某个字符串的位置值是原子 - > 呵呵（1）（意恒的）
• 如果（）语句都是原子 - > 呵呵（1）（意恒）
• 删除字符是原子 - > 呵呵（1）（意恒的）
• 您的for循环有呵呵（N）（依据n 的）

概括起来，你会得到呵呵（N）。

---

如果你想在Python中实现这一点，您可以使用 http://dog-net.org/ string.php ，以验证您的台阶。 :-)

---

PS：我不是在提供的复制和;粘贴的有目的的解决方案！ ：P

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

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