字符串金字塔转移矩阵
问题描述:
嗨刚刚看到有关NFA到DFA字符串金字塔转移矩阵
问题一个问题:给定叶节点的金字塔列表和地图指示什么是赋予左右节点的可能父节点。如果一个叶子节点可以变成根节点,则返回true,否则返回false。
实施例:
root
/\
X X
/\ /\
X X X
/\/ \/ \
A B C D
地图:
left: A | B | C | D
right---------------------------------
A B |A or C| D | A
B D |B or C| A |
C B
D
注:1。如果左边的孩子是B,右边的孩子是A,父亲节点可能是B或C
答
def generate_status(all_status, matrix):
# print all_status
if len(all_status) == 1:
return all_status[0]
next_all_status = []
for i in xrange(len(all_status) - 1):
cur_status = set()
for first_status in all_status:
for second_status in all_status[i+1]:
cur_status |= set(list(matrix[first_status][second_status]))
next_all_status.append(cur_status)
return generate_status(next_all_status, matrix)
def is_legal_status(expression, status, matrix):
all_status = [set(s) for s in expression]
return status in generate_status(all_status, matrix)
+0
您可以举一个输入数据的例子吗? – LeoShi
您是否试图根本解决问题? – synchronizer
是的,我有一个残酷的力量解决方案,但有人说有一个优化的方法。 – Newgod2500