Find number of combinations of strings This was an interview question I was asked. My answer is below, but I wonder if there is a more efficient way. Possible a combinatorics type function, or is an exhaustive generation + count the only way?

Rules: Given a character, the next character can be any one of How many N character combinations can you make? For example


a -> i,e
e -> i,o
i -> a,e,o
u -> a,e,i,o
o -> i,u,o


For N = 1 possible string combinations are a , e, i ,o ,u
for N = 2 possible string combinations are [ai, ae], [ei ,eo] ,[ia , ie , io],[ua,ue,ui,uo],[oi,ou,oo]
and so on.
I solved it by constructing a tree and then counting the leaves

struct Node {
    Node(char v) : v_(v) {}
    void                     add_child(shared_ptr&lt;Node&gt; n) { children.emplace_back(n); }
    char                     v_ = 0;
    vector&lt;shared_ptr&lt;Node&gt;&gt; children;
};

void add_child(shared_ptr&lt;Node&gt; root, int n, int depth, const map&lt;char, vector&lt;char&gt;&gt; &amp;combo) {
    if (depth == n) return;
    auto ch = root-&gt;v_;
    auto it = combo.find(ch);
    for (auto ch : it-&gt;second) {
        //printf("Adding to %c to %c\n", ch, root-&gt;v_);
        root-&gt;add_child(make_shared&lt;Node&gt;(ch));
    }
    ++depth;
    for (auto &amp;child : root-&gt;children) { add_child(child, n, depth, combo); }
}

int count_leaf(shared_ptr&lt;Node&gt; root) {
    if (root-&gt;children.size() == 0) return 0;
    int sum = 0;
    for (auto &amp;child : root-&gt;children) sum += count_leaf(child);
    return sum &gt; 0 ? sum : root-&gt;children.size();
}
void password_combination() {   
    // Find combos until this depth
    int n = 3;

    map&lt;char, vector&lt;char&gt;&gt; combo;
    combo.insert(make_pair('a', vector&lt;char&gt;{'i', 'e'}));
    combo.insert(make_pair('e', vector&lt;char&gt;{'i', 'o'}));
    combo.insert(make_pair('i', vector&lt;char&gt;{'a', 'e', 'o'}));
    combo.insert(make_pair('u', vector&lt;char&gt;{'a', 'e', 'i', 'o'}));
    combo.insert(make_pair('o', vector&lt;char&gt;{'i', 'u', 'o'}));

    // Create a N depth tree and count leaves
    // Count all children until n = 3;
    auto root  = make_shared&lt;Node&gt;(0);
    int  depth = 0;
    for (auto &amp;c : combo) { root-&gt;add_child(make_shared&lt;Node&gt;(c.first)); }
    for (auto child : root-&gt;children) { add_child(child, n, depth, combo); }
    printf("%d\n", count_leaf(root));
}


Is there a better way. Critique on the code/bugs, and if there's a c++14 idiomatic way of doing it, even better.
TL;DR: dynamic programming.

If the alphabet has \$k\$ symbols (5 in the example), in the worst case there are \$k^N\$ possible strings and generating them is \$\Omega(k^N)\$. But it's possible to count them in \$O(k^2 N)\$ time and \$O(k^2 + N)\$ space using a simple dynamic programming approach.

The input gives the successor function: \$a\$ must be followed by one of \$\{i,e\}\$. The first step is to reverse that to get the predecessor function: \$a\$ must be preceded by one of \$\{i,u\}\$.

Then the number of strings of length \$l\$ which end in \$a\$ is \$1\$ if \$l=1\$, or the sum of the number of strings of length \$l-1\$ which end in \$i\$ or \$u\$ otherwise.



Actually, if \$N\$ is large enough relative to \$k\$ you can do even better with a more complicated approach. Treat it as a Markov chain and find a matrix power of the \$0-1\$ matrix which indicates the successor function. That takes \$O(\lg N)\$ matrix multiplications of a \$k\times k\$ matrix.