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

Question

我仍然没有通过测试

• "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 + )("；以及
• "large2 simple large negative test, 10K+1 ('s followed by 10K )'s + )( + ()"。在

有人能看出我的错误是什么吗？我写的代码适用于我测试的所有字符串。。。在

以下是任务说明：

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

我的解决方案是：

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

您正在从从左到右和从右到左-这将在^{上失败-即使它是有效的，因为您会将[与{}进行比较。（start = 1和{}）

---

作为口头描述，我将做以下几点：

• 创建第二个预期值字符串。（稍后解释）
• 当你找到一个左括号-比较，每当你找到一个右括号时，迭代给定的字符串来建立你的期望字符串。在

示例：给定的字符串是{([])]。在

for i in range(0, length):

• 如果左括号[，{，(将期望的右括号放在期望字符串的末尾。i、 例如]，}或{}
• 否则（：=如果右括号）：
  • 右括号匹配表达式字符串中的最后一个字符？->；从期望字符串中删除，继续。在
  • 右括号与期望字符串中的最后一个字符不匹配？->；无效格式
  • 期望字符串为空？->；无效格式
  • 已到达输入字符串结尾，期望字符串不为空？->；无效格式。在

它会像这样处理给定的字符串：

^{pr2}$

---

编辑：由于预期的“存储复杂性”也是Oh(n)（不计算输入参数），所以当给定的字符串有n的左括号时，您将恰好遇到Oh(n)的存储复杂性，这没问题。但你是ofc。应该使用第二个string，那么原因列表有开销。在

对于运行时的复杂性：

• 在某个字符串位置设置值是原子的->；Oh(1)（表示常量）
• if()语句是原子的->；Oh(1)（表示常量）
• 删除字符是原子的->；Oh(1)（表示常量）
• for循环有Oh(n)（取决于n）

总结一下，你会得到Oh(n)。在

---

如果您想在Python中实现这一点，可以使用http://dog-net.org/string.php来验证您的“步骤”。：-）

---

注：我不是故意提供复制和粘贴解决方案！：P