leetcode Valid Parentheses

leetcode非常经典的算法题，Valid Parentheses,大意就是验证括号是否是符合匹配配对规则的，例如()[]是相互配对的,但是([)]就不是相互配对的了。 此题已经将范围缩小到字符串只包含大中小三种括号的字符了，所以只需要去考虑如何计算是否匹配了。

方案

这里资源最小，速度最快的方案是用到了所谓的栈技术。 我们假设”()[]{}”这种情况，可以知道这是符合配对规则的。首先第一个字符是(,我们把它丢到一个数组[’(‘],这时候这个数组包含括号的左边，然后第二个字符是)，而)和(是配对的，我们假设这是个消消乐的游戏，配对的连在一起了就消失了，所以数组[’(‘,’)’]发生这种情况的时候就消消乐了，配对的消失了，又变成空数组[]了。 也就是每次提取一个括号的时候，我们看下数组中的最后一个元素是不是配对的就行了，如果是配对的，就这两个元素一起扔掉，如果不是配对的，就继续往数组里扔进去。所以这种方法只需要对字符串循环一遍就行了，复杂度为O（n）。我们最后只需要判断下数组是不是为空就行了，为空就意味着全都消消乐了，括号全都配对，非空就是不配对。

def is_valid(s)
    arr = []
    s.chars.each do |e|
       last = arr.last
       if last == '(' && e == ')' or last == '[' && e == ']' or last == '{' && e == '}'
         arr.pop
       else
         arr << e
       end
    end
    arr.empty?
end

其他方案

上面我们是按照栈的方式去解，然后还有个有趣的方法，就是替换的方式。 因为题目中限定了字符串的范围都是括号，没有其他字符，所以，假设有个字符([]){}，我们怎么去判断是否符合规则呢？ 首先，([]){}本身就直接包含了配对括号，[]和{}，小括号()其实也是配对的，只不过是嵌套在了括号里，如果我们把符合配对的[]去掉，字符串就成了(){}，小括号就去掉了嵌套而暴露出来了。 所以我们只需要不停的对暴露出来的配对括号去掉就行了，如果全都配对，那么到最后，这个字符串一定会变成一个空字符串，相反如果不配对的，因为无法去除括号，所以肯定不能是空的，比如到最后’)(‘这种字符就无法根据配对的规则去除了。 这种方法的实现也非常简单，就是一直循环到没有配对的括号为止，最后看字符串是否为空。当然这种方式因为涉及到正则和循环，复杂度肯定是比栈的方法要废资源的，从提交的时间上也可以反应出来，不过这不失为一种思维方式。

# @param {String} s
# @return {Boolean}
def is_valid(s)
    while s.gsub!(/{}/,'') || s.gsub!(/\[\]/,'') || s.gsub!(/\(\)/,'')
    end
    s.empty?
end