寻找一个有效的子串

Question

最近遇到的一个练习让我有点困惑。

这似乎是一项简单的任务，我已经提出了我的解决方案，但结果并没有通过所有测试:D

在示例中，我找到了两个示例子字符串：

Input: S = "(()("
Output: 2
Explanation: The longest valid 
substring is "()". Length = 2.

和

Input: S = "()(())("
Output: 6
Explanation: The longest valid 
substring is "()(())". Length = 6.

一看就明白了

我想出了我的解决方案：

class Solution {

  findMaxLen(s) {
    if (!s || !s.length) throw new Error('Invalid input value provided')

    let openIndex = null
    let closingIndex = null

    for (let i = 0; i < s.length; i++) {
      if (s[i] == '(' && !openIndex) openIndex = i + 1
      if (s[i] == ')') closingIndex = i + 1
    }

    if(!closingIndex || !openIndex) throw new Error('Invalid substring')

    return closingIndex - openIndex + 1
  }
}

所以，我的解决方案应该解决试图用左括号和右括号查找 The longest substring 的问题。

但是它没有通过输入值的测试：(((() 正确答案是 2 而我的输出是 5

这个 (((() 与示例中提供的 ()(())( 不同吗？

我想我不完全理解子字符串是什么的想法...

Answer 1

这个伪代码应该可以工作。一些错误或边缘情况可能有松散的结局，因为我只是在此处临时写下的。随意测试它并指出遗漏。

helper_stack = null
max_valid_len = 0
running_len = 0

for i=0 to input_s.length:
    if helper_stack.length == 0:
        if input_s[i] == ')':
            running_len = 0
            continue
        else:
            helper_stack.push('(')
    else:
        if input_s[i] == '(':
            helper_stack.push('(')
        else:
            helper_stack.pop()
            running_len += 2
            if running_len > max_valid_len:
                max_valid_len = running_len

编辑：解释

根据您的逻辑，您没有跟踪括号 opening and closing 的顺序，这很重要。如果 closing bracket 在 open 之前，则字符串默认无效。因此，在这里使用堆栈是有意义的。

如果我们在打开之前遇到右括号，我们会从那一点重新开始。因此，我们设置running_len = 0。每次遇到右括号，如果有一个左括号来平衡它，我们就把它弹出，因为它是一对（字符，当我们考虑字符串的长度时），running_len += 2 就完成了。

只需稍作修改，我们甚至可以根据需要重现 max_valid_substring。然而，在我们的例子中，我们甚至可以只使用一个整数而不是 helper_stack。对于每个 push('(') 操作，只需执行 var += 1，对 pop 执行 var -= 1，这也应该可以解决问题。请注意，在这里，我们没有明确使用 stack，但这在概念上仍然是 LIFO = last in first out，基本上就是 stack.

寻找一个有效的子串

Finding a valid substring

javascript

algorithm

substring

编辑：解释