When the branching factor comes from the data

Nothing new in the search. The choices at each level are looked up rather than computed.

Key idea

Each level has its own option set

So far each level chose from the same pool. Some problems give a different set of options per level, supplied by a lookup table keyed on the input.

The search is unchanged. The only difference is where the loop gets its choices, and the depth of the recursion is the length of the input rather than a fixed size.

1OPTIONS = {"a": "12", "b": "34", "c": "5"}2 3def expansions(text):4    if not text:5        return []6    results, current = [], []7 8    def explore(index):9        if index == len(text):10            results.append("".join(current))11            return12        for choice in OPTIONS[text[index]]:13            current.append(choice)14            explore(index + 1)15            current.pop()16 17    explore(0)18    return results19 20print(expansions("ab"))21print(expansions("c"), expansions(""))

Predict the output· 5 min

Predict the output: where the size of the answer comes from

Each level of the search draws its choices from a table keyed on the input. Type the three lines it prints.

Python

1OPTIONS = {"a": "12", "b": "345", "c": "6"}2 3for text in ("ab", "abc", "c"):4    counts = [len(OPTIONS[ch]) for ch in text]5    total = 16    for count in counts:7        total *= count8    print(text, "->", counts, "->", total, "results")

Printed output

Problem· 20 min

Letter Combinations Of A Phone Number

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1OPTIONS = {"a": "12", "b": "34", "c": "5"}2 3def expansions(text):4 if not text:5 return []6 results, current = [], []7 8 def explore(index):9 if index == len(text):10 results.append("".join(current))11 return12 for choice in OPTIONS[text[index]]:13 current.append(choice)14 explore(index + 1)15 current.pop()16 17 explore(0)18 return results19 20print(expansions("ab"))21print(expansions("c"), expansions(""))

1OPTIONS = {"a": "12", "b": "345", "c": "6"}2 3for text in ("ab", "abc", "c"):4 counts = [len(OPTIONS[ch]) for ch in text]5 total = 16 for count in counts:7 total *= count8 print(text, "->", counts, "->", total, "results")