问题就是清除掉多余的括号。字符串里可能会有除括号外的其他字符。返回一个possible就可以不是返回所有的。
我的思路是一个stack辅助，保存left，遇到right如果stack为空则去掉这个right，如果不为空就pop。最后stack里面的剩下的就是invalid的left需要去掉。这么做有一些catch，第一就是你不能在push left的过程中直接remove right，否则stack存的index都乱了，因为我们动态修改了字符串长度。所以遇到非法right要先标记特殊字符然后最后再删掉。 最后删掉的时候也要注意其实还是在动态修改长度，index要记得再i 减减才可以继续循环（这个我忽略了）。
然后被问了一个不用stack的解法。没能自己想出来，给了提示。说，其实我们不用去记住left的每一个index。最左边的括号可以考虑是可以match anything的。这是他原话，没有让我明白其实。后来再经过例子的提示，明白了解法。 左边的有几个就需要有几个右边的来match，如果没有match的就是invalid的。那么我们仅需要统计左边和右边括号的数量，然后如果左边的多那就从后往前遍历数组，删掉前n个，n为左右数量差值。如果需要删掉右边的，那就从前往后遍历。
这个方法真心不错，之前练习的时候从来没想过这个思路，还是蛮开心的能学到东西。希望下一次学东西不是在面试现场啊。。这次能不能通过就看缘分吧，希望能继续下去!
Read full article from 记一次面试经历 – DeReK – Medium
No comments:
Post a Comment