文章/答案/技术大牛

发布

社区首页 >问答首页 >平衡括号的打印组合

问平衡括号的打印组合
EN

Code Review用户

提问于 2017-04-17 22:12:51

回答 1查看 406关注 0票数 5

解决了以下问题。希望听到您的反馈，特别是关于性能改进的反馈(当然，解决方案应该是递归的)。

特别关注的是，为了防止重复，我必须添加obj.include? elem检查。没有它就没有更好的方法了。

# Implement an algorithm to print all valid (e.g., properly 
# opened and closed) combinations of n-pairs of parentheses.
# EXAMPLE
# Input: 3
# Output: ((())), (()()), (())(), ()(()), ()()()

def brackets(n)
  return ["()"] if n == 1

  brackets(n-1).each_with_object([]) do |p, obj|
    for i in 0..p.length
      # stuff the "()" in every possible position within 'p'
      elem = p.dup.insert(i, "()")
      obj << elem unless obj.include? elem
    end
  end
end

ruby

recursion

balanced-delimiters

回答 1

Code Review用户

回答已采纳

发布于 2017-04-18 00:58:04

这是个很好的解决办法！

有一件事情可能会加快速度，那就是使用Set；那么就不需要include?了。只需在结束时调用to_a (或者不调用，并返回一个Set --仍然适合该任务)。

另外，我将使用p.length.times { |i| ... }而不是for循环，并使两个变量名更具描述性(例如，p不是一个非常描述性的名称)。

require 'set'

def brackets(n)
  return ["()"] if n == 1

  brackets(n-1).each_with_object(Set.new) do |str, set|
    str.length.times do |i|
      set << str.dup.insert(i, "()")
    end
  end.to_a
end

或者，不转换为数组：

def brackets(n)
  return Set.new(["()"]) if n == 1

  brackets(n-1).each_with_object(Set.new) do |str, set|
    str.length.times do |i|
      set << str.dup.insert(i, "()")
    end
  end
end

brackets(3) # => #<Set: {"()()()", "(())()", "()(())", "(()())", "((()))"}>

避免重复的"()"字符串也很好。您可以将其作为参数，因此该方法可用于其他“对”，例如：

def brackets(n, pair = "()")
  return Set.new([pair]) if n == 1

  brackets(n-1, pair).each_with_object(Set.new) do |str, set|
    str.length.times do |i|
      set << str.dup.insert(i, pair)
    end
  end
end

brackets(3, "<>") # => #<Set: {"<><><>", "<<>><>", "<><<>>", "<<><>>", "<<<>>>"}>

或者你可以简单地把它变成一个常量，比如SINGLE_PAIR = "()".freeze。

票数 4

页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://codereview.stackexchange.com/questions/161046

复制

相似问题

问平衡括号的打印组合
EN

回答 1

Code Review用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问平衡括号的打印组合EN

回答 1

Code Review用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问平衡括号的打印组合
EN