#!/usr/bin/python3
"See wordenum.go."

def get_words(d, pat):
    "Breadth-first, nonrecursive."
    result = [""]

    for patchar in pat:
        nr = []
        for s in result:
            for wc in d[patchar]:
                nr.append(s + wc)
        result = nr

    return result


def get_words_dg(d, pat):
    "Depth-first, linear-space, using generators instead of channels."
    def cvisitor(prefix, pat):
        if not pat:
            yield prefix
            return

        for c in d[pat[0]]:
            # Note that pat[1:] in Python is O(N) because it actually
            # copies the string, not O(1) as in Golang.
            yield from cvisitor(prefix + c, pat[1:])

    yield from cvisitor("", pat)


if __name__ == '__main__':
    print(get_words({"1": ["a", "b"], "2": ["c", "d"]}, "122"))
    print(list(get_words_dg({"1": ["a", "b"], "2": ["c", "d"]}, "122")))