Find number of combinations of strings

Question

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<Node> n) { children.emplace_back(n); }
 char v_ = 0;
 vector<shared_ptr<Node>> children;
};
void add_child(shared_ptr<Node> root, int n, int depth, const map<char, vector<char>> &combo) {
 if (depth == n) return;
 auto ch = root->v_;
 auto it = combo.find(ch);
 for (auto ch : it->second) {
 //printf("Adding to %c to %c\n", ch, root->v_);
 root->add_child(make_shared<Node>(ch));
 }
 ++depth;
 for (auto &child : root->children) { add_child(child, n, depth, combo); }
}
int count_leaf(shared_ptr<Node> root) {
 if (root->children.size() == 0) return 0;
 int sum = 0;
 for (auto &child : root->children) sum += count_leaf(child);
 return sum > 0 ? sum : root->children.size();
}
void password_combination() { 
 // Find combos until this depth
 int n = 3;
 map<char, vector<char>> combo;
 combo.insert(make_pair('a', vector<char>{'i', 'e'}));
 combo.insert(make_pair('e', vector<char>{'i', 'o'}));
 combo.insert(make_pair('i', vector<char>{'a', 'e', 'o'}));
 combo.insert(make_pair('u', vector<char>{'a', 'e', 'i', 'o'}));
 combo.insert(make_pair('o', vector<char>{'i', 'u', 'o'}));
 // Create a N depth tree and count leaves
 // Count all children until n = 3;
 auto root = make_shared<Node>(0);
 int depth = 0;
 for (auto &c : combo) { root->add_child(make_shared<Node>(c.first)); }
 for (auto child : root->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.

• yuri: Do you know yet if your solution passed?
• Delta_Fore: @yuri Not yet, but so far, not found any obvious bugs

Answer 1

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.

• Deduplicator: We can actually use the successor-function directly.