CS61A_HW04

Q6 题目描述：

Write a function has_path that takes in a tree t and a string phrase. It returns True if there is a path that starts from the root where the entries along the path spell out the phrase, and False otherwise. (This data structure is called a trie, and it has a lot of cool applications!---think autocomplete). You may assume that every node's label is exactly one character.

代码：

def has_path(t, phrase):
    """Return whether there is a path in a tree where the entries along the path
    spell out a particular phrase.

    >>> greetings = tree('h', [tree('i'),
    ...                        tree('e', [tree('l', [tree('l', [tree('o')])]),
    ...                                   tree('y')])])
    >>> print_tree(greetings)
    h
      i
      e
        l
          l
            o
        y
    >>> has_path(greetings, 'h')
    True
    >>> has_path(greetings, 'i')
    False
    >>> has_path(greetings, 'hi')
    True
    >>> has_path(greetings, 'hello')
    True
    >>> has_path(greetings, 'hey')
    True
    >>> has_path(greetings, 'bye')
    False
    """
    assert len(phrase) > 0, 'no path for empty phrases.'
    "*** YOUR CODE HERE ***"
    if len(phrase)==1:
        return phrase[0]==label(t)
    else:
        return label(t)==phrase[0] and any(has_path(branch,phrase[1:]) for branch in branches(t))

ps:

any 方法的使用：

any() 函数用于判断给定的可迭代参数 iterable 是否全部为 False，则返回 False，如果有一个为 True，则返回 True。

元素除了是 0、空、FALSE 外都算 TRUE。

any等价于：

def any(iterable):
    for element in iterable:
        if element:
            return True
    return False

类似的：

all() 函数用于判断给定的可迭代参数 iterable 中的所有元素是否都为 TRUE，如果是返回 True，否则返回 False。

元素除了是 0、空、None、False 外都算 True。