Question

2227. 加密解密字符串

English Version

题目描述

给你一个字符数组 keys ，由若干 互不相同 的字符组成。还有一个字符串数组 values ，内含若干长度为 2 的字符串。另给你一个字符串数组 dictionary ，包含解密后所有允许的原字符串。请你设计并实现一个支持加密及解密下标从 0 开始字符串的数据结构。

字符串 加密 按下述步骤进行：

1. 对字符串中的每个字符 c ，先从 keys 中找出满足 keys[i] == c 的下标 i 。
2. 在字符串中，用 values[i] 替换字符 c 。

字符串 解密 按下述步骤进行：

1. 将字符串每相邻 2 个字符划分为一个子字符串，对于每个子字符串 s ，找出满足 values[i] == s 的一个下标 i 。如果存在多个有效的 i ，从中选择 任意 一个。这意味着一个字符串解密可能得到多个解密字符串。
2. 在字符串中，用 keys[i] 替换 s 。

实现 Encrypter 类：

• Encrypter(char[] keys, String[] values, String[] dictionary) 用 keys、values 和 dictionary 初始化 Encrypter 类。
• String encrypt(String word1) 按上述加密过程完成对 word1 的加密，并返回加密后的字符串。
• int decrypt(String word2) 统计并返回可以由 word2 解密得到且出现在 dictionary 中的字符串数目。

 

示例：

输入：
["Encrypter", "encrypt", "decrypt"]
[[['a', 'b', 'c', 'd'], ["ei", "zf", "ei", "am"], ["abcd", "acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"]], ["abcd"], ["eizfeiam"]]
输出：
[null, "eizfeiam", 2]

解释：
Encrypter encrypter = new Encrypter([['a', 'b', 'c', 'd'], ["ei", "zf", "ei", "am"], ["abcd", "acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"]);
encrypter.encrypt("abcd"); // 返回 "eizfeiam"。 
               // 'a' 映射为 "ei"，'b' 映射为 "zf"，'c' 映射为 "ei"，'d' 映射为 "am"。
encrypter.decrypt("eizfeiam"); // return 2. 
                // "ei" 可以映射为 'a' 或 'c'，"zf" 映射为 'b'，"am" 映射为 'd'。 
                // 因此，解密后可以得到的字符串是 "abad"，"cbad"，"abcd" 和 "cbcd"。 
                // 其中 2 个字符串，"abad" 和 "abcd"，在 dictionary 中出现，所以答案是 2 。

 

提示：

• 1 <= keys.length == values.length <= 26
• values[i].length == 2
• 1 <= dictionary.length <= 100
• 1 <= dictionary[i].length <= 100
• 所有 keys[i] 和 dictionary[i] 互不相同
• 1 <= word1.length <= 2000
• 1 <= word2.length <= 200
• 所有 word1[i] 都出现在 keys 中
• word2.length 是偶数
• keys、values[i]、dictionary[i]、word1 和 word2 只含小写英文字母
• 至多调用 encrypt 和 decrypt 总计 200 次

解法

方法一：哈希表

class Encrypter:
  def __init__(self, keys: List[str], values: List[str], dictionary: List[str]):
    self.mp = dict(zip(keys, values))
    self.cnt = Counter(self.encrypt(v) for v in dictionary)

  def encrypt(self, word1: str) -> str:
    res = []
    for c in word1:
      if c not in self.mp:
        return ''
      res.append(self.mp[c])
    return ''.join(res)

  def decrypt(self, word2: str) -> int:
    return self.cnt[word2]


# Your Encrypter object will be instantiated and called as such:
# obj = Encrypter(keys, values, dictionary)
# param_1 = obj.encrypt(word1)
# param_2 = obj.decrypt(word2)

class Encrypter {
  private Map<Character, String> mp = new HashMap<>();
  private Map<String, Integer> cnt = new HashMap<>();

  public Encrypter(char[] keys, String[] values, String[] dictionary) {
    for (int i = 0; i < keys.length; ++i) {
      mp.put(keys[i], values[i]);
    }
    for (String w : dictionary) {
      w = encrypt(w);
      cnt.put(w, cnt.getOrDefault(w, 0) + 1);
    }
  }

  public String encrypt(String word1) {
    StringBuilder sb = new StringBuilder();
    for (char c : word1.toCharArray()) {
      if (!mp.containsKey(c)) {
        return "";
      }
      sb.append(mp.get(c));
    }
    return sb.toString();
  }

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

/**
 * Your Encrypter object will be instantiated and called as such:
 * Encrypter obj = new Encrypter(keys, values, dictionary);
 * String param_1 = obj.encrypt(word1);
 * int param_2 = obj.decrypt(word2);
 */

class Encrypter {
public:
  unordered_map<string, int> cnt;
  unordered_map<char, string> mp;

  Encrypter(vector<char>& keys, vector<string>& values, vector<string>& dictionary) {
    for (int i = 0; i < keys.size(); ++i) mp[keys[i]] = values[i];
    for (auto v : dictionary) cnt[encrypt(v)]++;
  }

  string encrypt(string word1) {
    string res = "";
    for (char c : word1) {
      if (!mp.count(c)) return "";
      res += mp[c];
    }
    return res;
  }

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

/**
 * Your Encrypter object will be instantiated and called as such:
 * Encrypter* obj = new Encrypter(keys, values, dictionary);
 * string param_1 = obj->encrypt(word1);
 * int param_2 = obj->decrypt(word2);
 */

type Encrypter struct {
  mp  map[byte]string
  cnt map[string]int
}

func Constructor(keys []byte, values []string, dictionary []string) Encrypter {
  mp := map[byte]string{}
  cnt := map[string]int{}
  for i, k := range keys {
    mp[k] = values[i]
  }
  e := Encrypter{mp, cnt}
  for _, v := range dictionary {
    e.cnt[e.Encrypt(v)]++
  }
  return e
}

func (this *Encrypter) Encrypt(word1 string) string {
  var ans strings.Builder
  for _, c := range word1 {
    if v, ok := this.mp[byte(c)]; ok {
      ans.WriteString(v)
    } else {
      return ""
    }
  }
  return ans.String()
}

func (this *Encrypter) Decrypt(word2 string) int {
  return this.cnt[word2]
}

/**
 * Your Encrypter object will be instantiated and called as such:
 * obj := Constructor(keys, values, dictionary);
 * param_1 := obj.Encrypt(word1);
 * param_2 := obj.Decrypt(word2);
 */