algorithm - 字符串金字塔转移矩阵

Question

你好刚刚看到一个与 NFA 到 DFA 相关的问题

问题:给定一个金字塔中的叶节点列表，以及一个映射，该映射指示给定左节点和右节点的可能父节点。如果叶节点之一可以变成根节点，则返回true，否则返回false。

例子:

     root
     / \
    X   X
   /\  /\
   X  X  X
  / \/ \/ \
 A   B  C  D

map :

        left: A |  B   |   C | D
right---------------------------------
A             B |A or C|   D | A
B             D |B or C|   A |
C                              B
D

注:1。如果左 child 是B，右 child 是A，父节点可能是B或C

Answer 1

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)