m***u
发帖数: 35 | 1 二面，挂了，不会做，求高手指导：
Balanced String
Q: Given a String s, determine whether it is balanced or not.
Definition of balanced:
1) "" or ":"
2) Balanced String + Balanced String
3) "(" + Balanced String + ")"
4) ":)" or ":(" |
z*******o
发帖数: 4773 | |
d******b
发帖数: 73 | 3 这个就是解析 一个context free grammar, 学过编译原理的 应该可以秒过。
S -> SS
-> ( S )
-> :( | :) | : | epsilon |
Q**F
发帖数: 995 | |
y*****e
发帖数: 712 | |
t*********r
发帖数: 387 | 6 最优解
不过估计一半码农看不懂，碰到个阿三或者老将就跪了
【在 d******b 的大作中提到】
: 这个就是解析 一个context free grammar, 学过编译原理的 应该可以秒过。
: S -> SS
: -> ( S )
: -> :( | :) | : | epsilon
|
n****5
发帖数: 81 | 7 让bison去产生parser code？还是要自己写递归吧？
【在 d******b 的大作中提到】
: 这个就是解析 一个context free grammar, 学过编译原理的 应该可以秒过。
: S -> SS
: -> ( S )
: -> :( | :) | : | epsilon
|
j**********3
发帖数: 3211 | |
S**********5
发帖数: 896 | 9 中间是个镜子，左右就是镜子的折射？题目是这样意思吗？我没看懂 |
d******e
发帖数: 2265 | 10 def balanced(s):
if s in ["", ":)", ":(", ":"]:
return True
elif s[0] == "(" and s[-1] == ")" and balanced(s[1:-1]):
return True
elif any([balanced(s[:k]) and balanced(s[k:]) for k in range(1, len(s))
]):
return True
else:
return False
naive写法。
【在 m***u 的大作中提到】
: 二面，挂了，不会做，求高手指导：
: Balanced String
:
: Q: Given a String s, determine whether it is balanced or not.
:
: Definition of balanced:
: 1) "" or ":"
: 2) Balanced String + Balanced String
: 3) "(" + Balanced String + ")"
: 4) ":)" or ":("
|
