2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Do you know yet if your solution passed? \$\endgroup\$ – yuri Jul 11 '17 at 14:19
  • \$\begingroup\$ @yuri Not yet, but so far, not found any obvious bugs \$\endgroup\$ – Ronnie Jul 11 '17 at 14:21
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ We can actually use the successor-function directly. \$\endgroup\$ – Deduplicator Jul 11 '17 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.