字符串金字塔转移矩阵

问题一个问题：给定叶节点的金字塔列表和地图指示什么是赋予左右节点的可能父节点。如果一个叶子节点可以变成根节点，则返回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

来源

2017-04-16 Newgod2500

您是否试图根本解决问题？ – synchronizer

是的，我有一个残酷的力量解决方案，但有人说有一个优化的方法。 – Newgod2500

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)

来源

2017-04-16 01:27:06 Kevman

您可以举一个输入数据的例子吗？ – LeoShi

字符串金字塔转移矩阵

回答

相关问题