Python中的算法实现

Question

我有一定的算法需要实现。基本上这些规则是：

1. 一行上的第一个以空格分隔的标记将被定义的单词。
2. 后面的令牌将被定义。如果定义是“。”，则该单词是原语，即没有定义的单词。
3. 输出是一个逗号分隔的单行文本，其中只包含一次字典中的每个单词。每个单词只能在其定义中的所有单词后面打印。请注意，对于某些输入集，可能有多个有效输出。

例如输入：

Civic  Honda Car 
Honda  Manufacturer 
VW   Manufacturer 
Manufacturer . 
Car   . 
Beetle  VW Car 

一些可能的输出：

Car, Manufactor, Honda, VW, Beetle, Civic 
Manufacturer, VW, Car, Beetle, Honda, Civic 
Manufacturer, Honda, VW, Car, Beetle, Civic 

我的实现：

def defIt(pre, cur): 
    # If previous and current strings are the same, no action take 
    if pre == cur: 
     return pre 

    # Split two strings to list 
    l_pre = pre.split() 
    l_cur = cur.split() 

    # If previous string length is shorter than the current string  length, then swap two lists 
    if len(l_pre) < len(l_cur): 
     l_pre, l_cur = l_cur, l_pre 

    found = False 


    for j, w_cur in enumerate(l_cur): 
     for i, w_pre in enumerate(l_pre): 
      if w_pre == w_cur: 
       found = True 
       return ' '.join(l_cur[j:] + l_cur[:j] + l_pre[:i] + l_pre[(i + 1):]) 


    if not found: 
     return ' '.join(l_cur[1:] + [l_cur[0]] + l_pre) 

只是无法得到它的权利。我错过了什么？非常感谢。

Answer 1

def read_graph(lines): 
    g = {} 
    for line in lines: 
     words = line.split() 
     if words[1] == '.': 
      words = words[:1] 
     g[words[0]] = words[1:] 
    return g 

def dump_graph(g): 
    out = [] 
    def dump(key): 
     for k in g[key]: 
      dump(k) 
     if key not in out: 
      out.append(key) 
    for k in g: 
     dump(k) 
    return out 

用法：

>>> data = """Civic  Honda Car 
... Honda  Manufacturer 
... VW   Manufacturer 
... Manufacturer . 
... Car   . 
... Beetle  VW Car 
... """ 
>>> g = read_graph(data.splitlines()) 
>>> g 
{'VW': ['Manufacturer'], 'Civic': ['Honda', 'Car'], 'Car': [], 
'Honda': ['Manufacturer'], 'Beetle': ['VW', 'Car'], 'Manufacturer': []} 
>>> dump_graph(g) 
['Manufacturer', 'VW', 'Honda', 'Car', 'Civic', 'Beetle'] 
>>> 

在结果列表中的每一个字谈到毕竟它的 “定义” 的话。