题解 | #某度短网址#

class Solution {
public:
vector<string> urlTransformation(vector<string> &long_url, vector<string> &short_url)
{
  static long mod = 56800235584;
  static std::string table = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
  std::unordered_map<long, std::string> key_long_hash;  // key和长网址绑定
  std::unordered_map<std::string, long> short_key_hash; // 短网址和key绑定
  auto generate_short_url = [](long key)
  {
    std::string url(6, '0');
    int index = 6;
    while (key > 0)
    {
      url[--index] = table[key % 62];
      key /= 62;
    }
    return url;
  };

  auto calc_key = [&key_long_hash](const std::string &url) -> long
  {
    long key = 0;
    for (auto c : url)
    {
      key = (key * 64 + c) % mod;
    }

    while (key_long_hash.find(key) != key_long_hash.end())
    {
      key = (key + 1) % mod;
    }
    return key;
  };

  std::vector<std::string> ans;
  std::string prefix = "http://tiny.url";
  for (auto &url : long_url)
  {
    long key = calc_key(url);
    auto s = generate_short_url(key);
    key_long_hash[key] = url;
    short_key_hash[s] = key;
    ans.push_back(prefix + s);
  }

  for (auto &url : short_url)
  {
    auto pos = url.find(prefix);
    if (pos == url.npos)
    {
      continue;
    }
    auto s = url.substr(pos + prefix.size());
    if (short_key_hash.find(s) != short_key_hash.end())
    {
      ans.push_back(key_long_hash[short_key_hash[s]]);
    }
  }
  return ans;
}
};