2227. 加密解密字符串

题目

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

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

对字符串中的每个字符 c ，先从 keys 中找出满足 keys[i] == c 的下标 i 。
在字符串中，用 values[i] 替换字符 c 。
字符串 解密 按下述步骤进行：

将字符串每相邻 2 个字符划分为一个子字符串，对于每个子字符串 s ，找出满足 values[i] == s 的一个下标 i 。如果存在多个有效的 i ，从中选择 任意 一个。这意味着一个字符串解密可能得到多个解密字符串。
在字符串中，用 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 次

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/encrypt-and-decrypt-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

加密过程比较简单，按照和的对应关系拼接字符串即可。

注意到有重复的值，即和是多对一的关系，因此一个加密后的字符串可能对应多个原串。因此，解密过程如果按照常规思路进行解密，然后再和对照，需要使用和字典树(避免超时超内存)求解解密字符串对应的所有的原串。一个逆向的思路是对中所有字符串进行加密，记录加密后各个字符串出现的次数存在哈希表中，当调用#card=math&code=decrypt%28%29&id=QpLO0)函数直接返回该字符串在哈希表中对应的次数就行。

代码

class Encrypter {
    char[] key;
    // 记录keys和values的对应关系，一个key对应唯一的一个value
    Map<Character, String> enc = new HashMap<>();
    // 记录dictionary中字符串加密后字符串出现的次数
    Map<String, Integer> dec = new HashMap<>();
    public Encrypter(char[] keys, String[] values, String[] dictionary) {
        key = keys;
        int n = values.length;
        for (int i = 0; i < n; ++i) {
            enc.put(key[i], values[i]);
        }
        for (String str : dictionary) {
            String res = encrypt(str);
            if (!res.equals("")) {
                dec.put(res, dec.getOrDefault(res, 0) + 1);
            }
        }
    }
    public String encrypt(String word1) {
        StringBuilder sb = new StringBuilder();
        for (char c : word1.toCharArray()) {
            // word1中可能含有keys中不存在的字符，这种情况无法加密，返回空串
            if (enc.containsKey(c)) {
                sb.append(enc.get(c));
            } else {
                return "";
            }
        }
        return sb.toString();
    }
    public int decrypt(String word2) {
        return dec.getOrDefault(word2, 0);
    }
}