Leetcode匹配对

Question

match方法接受一个字符串和左括号的索引。该方法需要返回匹配括号的索引。如果给定的索引不是左括号，或者没有匹配的括号，则返回-1。请参见下面的示例。

Example:
ParenthesesMatcher.match("(())", 1) => 2
The given index is for the second parentheses. 
The matching is the closing parentheses at index 2.

ParenthesesMatcher.match("(())", 0) => 3
The given index is for the first parentheses. 
The matching is the last closing parentheses at index 3.

ParenthesesMatcher.match("asdf", 0) => -1
The given index is not an opening parentheses. Return -1.

ParenthesesMatcher.match("(()", 0) => -1
The given index does not have a matching parentheses. Return -1.

一致的解决方案#1:简短，单一方法，简单。

def match(string, start)
  return -1 unless str[start] == ?(
    open = 0
    str[start..-1].each_char.with_index do |c, i|
      if c == ?(
        open += 1
      elsif c == ?)
        open -= 1
        return start + i if open == 0
      end
    end

    -1
  end

end

Answer 1

这被标记为一个Ruby问题，所以我想我应该发布一个Ruby答案。我真的很喜欢上面@lincr的基于堆栈的方法，但我对它进行了一些简化。它分析输入字符串以生成每对参数的开始和结束偏移量的数组。然后它只是遍历列表，寻找匹配的起始点。

def paren_pairs(sample)
  pairs = []
  stack = []
  sample.chars.each_with_index do |chr, i|
    stack.push i if chr == '('
    pairs.append [stack.pop, i] if chr == ')'
  end
  pairs
end

def match_parens(sample, i)
  paren_pairs(sample).reduce(-1) { |result, pair| pair[0] == i ? pair[1] : result }
end

所以：

tests = [['(())', 1, 2],
         ['(())', 0, 3],
         ['asdf', 0, -1],
         ['(()', 0, -1]]

tests.each do |test|
  sample, index, expected = test
  puts "#{sample}, #{index}, expected #{expected}, got #{match_parens sample, index}"
end

结果：

(()), 1, expected 2, got 2
(()), 0, expected 3, got 3
asdf, 0, expected -1, got -1
((), 0, expected -1, got -1

Answer 2

我在这里编写了一个小的python程序来演示使用堆栈的想法。你保存堆栈中看到的'(‘的索引，当你看到一个')’出现时，你从堆栈中弹出一个'(‘。

def match_parentheses(s, index):
    stack = []
    marker = -1
    for i in range(len(s)):
        if i != index:
            if s[i] == '(':
                stack.append(i)
            elif s[i] == ')':

                # in our processed ()s, there are more ')' than '(',
                # just ignore it, the stack is guaranted to be empty 
                if len(stack) == 0:
                    continue
                peek = stack[-1]
                if marker >= 0 and peek == marker:
                    return i
                else:
                    stack.pop()
        else:
            if s[i] == ')':
                return stack[-1] if len(stack) > 0 else -1
            elif s[i] == '(':
                marker = i
                stack.append(i)
            else:
                return -1
    return -1
match_parentheses("(())", 1)
match_parentheses("(())", 0)
match_parentheses("abcd", 0)
match_parentheses("(()", 0)
match_parentheses("())", 2)
match_parentheses("(())()()", 7)

输出：

2 3 -1 -1 -1 6

Answer 3

好的，试着去理解。我看到字符串被作为数组处理，而不是键/值对。

我所做的，我知道，这是相当幼稚的，是首先检查以确保索引是一个开放的paren，然后在你遍历字符串/数组时递增和递减一个数字，从给定的索引开始，这样当你找到匹配的父代时，你就会达到0。比如，对于“()”，你想找到索引1的匹配项，你有一个名为inc的变量，它的初始值是0。在索引1处，它递增到1，在索引2到2处，在3到3处，在4到4处，在5处递减到3，在6到2处，在7到1处，在8到0处，因此8是对1的匹配。

我现在满脑子都是Java，想不出连贯的Ruby代码，最后我会扔进一堆随机的分号。

但感觉这并不是问题的全部。还有更多的解释吗？

顺便说一下，这个词是句法上的，而不是句法上的。