2227. Encrypt and Decrypt Strings

Approach 1: Trie

• Time:
  • Constructor: $O(|\texttt{keys}| + \Sigma |\texttt{dictionary[i]}|)$
  • encrypt(word1: str): $O(|\texttt{word1}|)$
  • decrypt(word2: str): $O(|\texttt{word2}| + \Sigma |\texttt{dictionary[i]}|)$
• Space: $O(\Sigma |\texttt{dictionary[i]}|)$

C++JavaPython

struct TrieNode {
  vector<shared_ptr<TrieNode>> children;
  bool isWord = false;
  TrieNode() : children(26) {}
};

class Encrypter {
 public:
  Encrypter(vector<char>& keys, vector<string>& values,
            vector<string>& dictionary) {
    for (int i = 0; i < keys.size(); ++i) {
      const char key = keys[i];
      const string& value = values[i];
      keyToValue[key] = value;
      valueToKeys[value].push_back(key);
    }
    for (const string& word : dictionary)
      insert(word);
  }

  string encrypt(string word1) {
    string ans;
    for (const char c : word1)
      ans += keyToValue[c];
    return ans;
  }

  int decrypt(string word2) {
    return find(word2, 0, root);
  }

 private:
  unordered_map<char, string> keyToValue;
  unordered_map<string, vector<char>> valueToKeys;
  shared_ptr<TrieNode> root = make_shared<TrieNode>();

  void insert(const string& word) {
    shared_ptr<TrieNode> node = root;
    for (const char c : word) {
      const int i = c - 'a';
      if (node->children[i] == nullptr)
        node->children[i] = make_shared<TrieNode>();
      node = node->children[i];
    }
    node->isWord = true;
  }

  int find(const string& word, int i, shared_ptr<TrieNode> node) {
    const string value = word.substr(i, 2);
    if (!valueToKeys.contains(value))
      return 0;

    int ans = 0;
    if (i + 2 == word.length()) {
      for (const char key : valueToKeys[value]) {
        const auto& child = node->children[key - 'a'];
        ans += child && child->isWord;
      }
      return ans;
    }

    for (const char key : valueToKeys[value]) {
      if (!node->children[key - 'a'])
        continue;
      ans += find(word, i + 2, node->children[key - 'a']);
    }

    return ans;
  }
};

class TrieNode {
  public TrieNode[] children = new TrieNode[26];
  public boolean isWord = false;
}

class Encrypter {
  public Encrypter(char[] keys, String[] values, String[] dictionary) {
    for (int i = 0; i < keys.length; ++i) {
      final char key = keys[i];
      final String value = values[i];
      keyToValue.put(key, value);
      valueToKeys.putIfAbsent(value, new ArrayList<>());
      valueToKeys.get(value).add(key);
    }
    for (final String word : dictionary)
      insert(word);
  }

  public String encrypt(String word1) {
    StringBuilder sb = new StringBuilder();
    for (final char c : word1.toCharArray())
      sb.append(keyToValue.get(c));
    return sb.toString();
  }

  public int decrypt(String word2) {
    return find(word2, 0, root);
  }

  private Map<Character, String> keyToValue = new HashMap<>();
  private Map<String, List<Character>> valueToKeys = new HashMap<>();
  private TrieNode root = new TrieNode();

  void insert(final String word) {
    TrieNode node = root;
    for (final char c : word.toCharArray()) {
      final int i = c - 'a';
      if (node.children[i] == null)
        node.children[i] = new TrieNode();
      node = node.children[i];
    }
    node.isWord = true;
  }

  int find(final String word, int i, TrieNode node) {
    final String value = word.substring(i, i + 2);
    if (!valueToKeys.containsKey(value))
      return 0;

    int ans = 0;
    if (i + 2 == word.length()) {
      for (final char key : valueToKeys.get(value)) {
        TrieNode child = node.children[key - 'a'];
        if (child != null && child.isWord)
          ++ans;
      }
      return ans;
    }

    for (final char key : valueToKeys.get(value)) {
      if (node.children[key - 'a'] == null)
        continue;
      ans += find(word, i + 2, node.children[key - 'a']);
    }

    return ans;
  }
}

class TrieNode:
  def __init__(self):
    self.children: dict[str, TrieNode] = collections.defaultdict(TrieNode)
    self.isWord = False


class Encrypter:
  def __init__(self, keys: list[str], values: list[str], dictionary: list[str]):
    self.keyToValue = {k: v for k, v in zip(keys, values)}
    self.valueToKeys = collections.defaultdict(list)
    self.root = TrieNode()
    for k, v in zip(keys, values):
      self.valueToKeys[v].append(k)
    for word in dictionary:
      self._insert(word)

  def encrypt(self, word1: str) -> str:
    return ''.join(self.keyToValue[c] for c in word1)

  def decrypt(self, word2: str) -> int:
    return self._find(word2, 0, self.root)

  def _insert(self, word: str) -> None:
    node = self.root
    for c in word:
      node = node.children.setdefault(c, TrieNode())
    node.isWord = True

  def _find(self, word: str, i: int, node: TrieNode) -> int:
    value = word[i:i + 2]
    if value not in self.valueToKeys:
      return 0

    ans = 0
    if i + 2 == len(word):
      for key in self.valueToKeys[value]:
        ans += node.children[key].isWord
      return ans

    for key in self.valueToKeys[value]:
      if key not in node.children:
        continue
      ans += self._find(word, i + 2, node.children[key])

    return ans

Approach 2: Hash Map

• Time:
  • Constructor: $O(|\texttt{keys}|)$
  • encrypt(word1: str): $O(|\texttt{word1}|)$
  • decrypt(word2: str): $O(1)$
• Space: $O(|\texttt{keys}|)$

C++JavaPython

class Encrypter {
 public:
  Encrypter(vector<char>& keys, vector<string>& values,
            vector<string>& dictionary) {
    for (int i = 0; i < keys.size(); ++i)
      keyToValue[keys[i]] = values[i];

    for (const string& word : dictionary)
      ++encryptedCount[encrypt(word)];
  }

  string encrypt(string word1) {
    string ans;
    for (const char c : word1)
      ans += keyToValue[c];
    return ans;
  }

  int decrypt(string word2) {
    return encryptedCount[word2];
  }

 private:
  unordered_map<char, string> keyToValue;
  unordered_map<string, int> encryptedCount;
};

class Encrypter {
  public Encrypter(char[] keys, String[] values, String[] dictionary) {
    for (int i = 0; i < keys.length; ++i)
      keyToValue.put(keys[i], values[i]);

    for (final String word : dictionary)
      encryptedCount.merge(encrypt(word), 1, Integer::sum);
  }

  public String encrypt(String word1) {
    StringBuilder sb = new StringBuilder();
    for (final char c : word1.toCharArray())
      sb.append(keyToValue.get(c));
    return sb.toString();
  }

  public int decrypt(String word2) {
    return encryptedCount.getOrDefault(word2, 0);
  }

  private Map<Character, String> keyToValue = new HashMap<>();
  private Map<String, Integer> encryptedCount = new HashMap<>();
}

class Encrypter:
  def __init__(self, keys: list[str], values: list[str], dictionary: list[str]):
    self.keyToValue = {k: v for k, v in zip(keys, values)}
    self.decrypt = collections.Counter(self.encrypt(word)
                                       for word in dictionary).__getitem__

  def encrypt(self, word1: str) -> str:
    return ''.join(self.keyToValue[c] for c in word1)