为什么这个解决方案会失败？嵌套和括号匹配

本文介绍了为什么这个解决方案会失败？嵌套和括号匹配的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我仍然失败测试

negative_match：无效的结构，;
simple_grouped：简单的分组正面和负面的测试，长度= 22;
large1简单大积极的测试，100K（的后面100K）的+）（和
large2简单较大的负测试，10K + 1（的后跟10K）的+）（+（）。

任何人都可以看到我的错误是？在code我写的作品，我测试了所有的字符串...

下面是任务的描述：

下面是我的解决办法：

 高清解决方案（S）：
＃写你的code在Python 2.7
若S ==：
    返回1
长度= len个（S）
启动= 0
结束=长度为1

如果长度％2 = 0！
    返回0

在我的范围（0，长度）：
    如果（S [开始] =='（'）和（S [结束] ='）'！）：
        返回0
    如果（S [开始] =='['（）和S [结束] =！']'）：
        返回0
    如果（S [开始] =='{'（）和S [结束] =！}）：
        返回0
    启动=启动+1
    结束=结束-1

返回1

通过

解决方案

您是从的左至右和右键寻求左的 - 这将失败（[] {}） - 即便其有效的，因为你会比较 [与} 。（启动= 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:

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

这篇关于为什么这个解决方案会失败？嵌套和括号匹配的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！

100k

为什么这个解决方案会失败？嵌套和括号匹配

问题描述