class Solution {
public:
  set<char> c_set;
  vector<char> c;
  set<char> no_zeros;
  map<char, int> l_factors;
  map<char, int> r_factors;
  set<int> used;
  
  bool isSolvable(vector<string>& words, string result) {
    for(int i = 0; i < words.size(); i++) {
      int factor = 1;
      for(int j = 0; j < words[i].size(); j++) {
        char tmp = words[i][words[i].size() - j - 1];
        if (j == words[i].size() - 1) {
          no_zeros.insert(tmp);
        }
        c_set.insert(tmp);
        
        if (l_factors.find(tmp) == l_factors.end()) {
          l_factors[tmp] = factor;
        } else {
          l_factors[tmp] += factor;
        }
        
        factor *= 10;
      }
    }
    for(int i = 0, factor = 1; i < result.size(); i++) {
      char tmp = result[result.size() - i - 1];
      if (i == result.size() - 1) {
        no_zeros.insert(tmp);
      }
      c_set.insert(tmp);
      if (r_factors.find(tmp) == r_factors.end()) {
        r_factors[tmp] = factor;
      } else {
        r_factors[tmp] += factor;
      }
      factor *= 10;
    }
    
    for(auto i : c_set) {
      c.push_back(i);
    }
    
    return dfs(0, 0, 0);
  }
  
  bool dfs(int r, int left, int right) {
    if (r == c.size()) {
      return left == right;
    }
    
    char tmp = c[r];
    int l_factor = 0;
    if (l_factors.find(tmp) != l_factors.end()) {
        l_factor = l_factors[tmp];
    }
    
    int r_factor = 0;
    if (r_factors.find(tmp) != r_factors.end()) {
      r_factor = r_factors[tmp];
    }
    
    for(int i = 0; i < 10; i++) {
      if (i == 0 && no_zeros.find(tmp) != no_zeros.end()) {
        continue;
      }
      if (used.find(i) != used.end()) {
        continue;
      }
      used.insert(i);
      
      if (dfs(r + 1, left + i * l_factor, right + i * r_factor)) {
        return true;
      }
      used.erase(i);
    }
    return false;
  }
};

#include <chrono>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <set>

using namespace std;

#define SIZE 10
#define PRE_FILL (SIZE / 2)
#define OP 1000000

set<int> test_set;
bool test_array[SIZE];

void set_find() {
  int count = 0;
  for(int i = 0; i < OP; i++) {
    int j = std::rand() % SIZE;
    if (test_set.find(j) != test_set.end()) {
      count += 1;
    }
  }
}

void array_find() {
  int count = 0;
  for(int i = 0; i < OP; i++) {
    int j = std::rand() % SIZE;
    if (test_array[j]) {
      count += 1;
    }
  }
}

void set_insert_and_delete() {
  for(int i = 0; i < OP; i++) {
      int j = std::rand() % SIZE;
      test_set.insert(j);
      test_set.erase(j);
  }
}

void array_insert_and_delete() {
  for(int i = 0; i < OP; i++) {
      int j = std::rand() % SIZE;
      test_array[j] = true;
      test_array[j] = false;
  }
}

void measure(string name, void (*func)()) {
  auto start = std::chrono::high_resolution_clock::now();
  
  func();
  
  auto finish = std::chrono::high_resolution_clock::now();
  std::chrono::duration<double> elapsed = finish - start;
  std::cout << name << ": " << elapsed.count() << " s\n";
}

int main(int argc, char *argv[]) {
  std::srand(std::time(nullptr)); // use current time as seed for random generator

  memset(test_array, 0, sizeof test_array);
  
  for(int i = 0; i < PRE_FILL; i++) {
      int j = std::rand() % SIZE;
      test_set.insert(j);
      test_array[j] = true;
  }

  measure("set_find", set_find);
  measure("array_find", array_find);
  measure("set_insert_and_delete", set_insert_and_delete);
  measure("array_insert_and_delete", array_insert_and_delete);
}