Expand a wildcard ticker pattern into all matches

Question

A symbol pattern is given as a list where each position holds the set of characters allowed there. Enumerate every concrete symbol the pattern can produce, in order.

options = ["AB", "12"]
-> ["A1", "A2", "B1", "B2"]

Return all strings formed by choosing one character from each position (their Cartesian product).

Accepted Answer

Backtrack position by position. At position pos, try each allowed character, append it, recurse to the next position, then pop it. When pos runs past the last position, the buffer holds one complete symbol, record it. Iterating the options in given order makes the output order predictable. Tracing ["AB", "12"]: fixing A gives "A1" and "A2"; fixing B gives "B1" and "B2". Time O(product of the option-set sizes, times the length), space O(number of positions) recursion depth. Edge cases: an empty options list yields one empty string [""]; if any position has no allowed characters, the product is…

Expand a wildcard ticker pattern into all matches

Your answer

More Coding questions