字符串金字塔轉移矩陣

問題一個問題：給定葉節點的金字塔列表和地圖指示什麼是賦予左右節點的可能父節點。如果一個葉子節點可以變成根節點，則返回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

字符串金字塔轉移矩陣

回答

相關問題