Amazon | Build target string using baby blocks
Anonymous User
4933
Interview

Problem
You have a collection of baby blocks (cubes with single upper-case letters of the alphabet on each side).

Each block could have up to six different letters on it (or even more if we're in a universe with more than 3 dimensions),
but for the sake of simplicity, we'll assume for now that each block only has two distinct letters.

The problem is to write a function that takes a collection of blocks and a target word and
returns true or false depending on whether or not you can spell the target word with the collection of blocks.

Example:
(B,A),(A,B),(X,Y),(A,B): "BABY" => true
(B,A),(A,B),(L,E),(A,B): "ABLE" => false (since L and E are on the same block).

Possible solution
I wonder if my solution below is correct and how it can be further optimized. Thoughts?

#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>

using namespace std;
typedef string block;

// using memoization
// helper function
bool can_build(string& target, unordered_multiset<block>& blocks_rem,
               string& cur, 
               unordered_map<char, unordered_set<block>>& blocks_map,
               unordered_map<size_t, unordered_map<block, bool>>& memo) {
  size_t pos = cur.size();
  if (cur == target) return true;
  if (pos > target.size()) return false;

  char target_char = target[pos];
  if (blocks_map.count(target_char) == 0) return false;

  for (const block& b : blocks_map[target_char]) {
    // if there is at least one unused block which contains letter target_char
    if (blocks_rem.find(b) != blocks_rem.end()) { 
      if (memo.count(pos) && memo[pos].count(b)) return memo[pos][b];
      blocks_rem.erase(blocks_rem.find(b));
      cur.push_back(target_char);
      if (can_build(target, blocks_rem, cur, blocks_map, memo)) 
        return memo[pos][b] = true;
      cur.pop_back();
      blocks_rem.insert(b);
    }
    memo[pos][b] = false;
  }
  return false;
}

bool can_build_string_memo(string& target, vector<block>& blocks) {
  if (blocks.size() < target.size()) {
    return false;
  }
  unordered_map<char, unordered_set<block>> blocks_map;
  unordered_multiset<block> blocks_left;
  unordered_map<size_t, unordered_map<block, bool>> memo;
  for (block& b : blocks) {
    sort(begin(b), end(b));
    for (char c : b) blocks_map[c].insert(b);
    blocks_left.insert(b);
  }
  string s;
  return can_build(target, blocks_left, s, blocks_map, memo);
}
Comments (4)