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']
>>>

结果列表中的每个词都是在它所有的“定义”词之后出现的。