2227. 加密和解密字符串

Hard

题目描述

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

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

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

注意，如果字符串中的某个字符 不存在 于 keys 中，则无法执行加密过程，返回空字符串 "" 。

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

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

请你实现 Encrypter 类：

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

示例 1：

输入：
["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"); // 返回 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
2 <= word2.length <= 200
所有 word1[i] 都出现在 keys 中
word2.length 是偶数
keys 、values[i] 、dictionary[i] 、word1 和 word2 只含小写英文字母
至多调用 encrypt 和 decrypt 总计 200 次

解题思路

这道题要求我们实现一个加密解密系统。关键思路如下：

加密过程比较直观：建立字符到加密字符串的映射表，逐一替换即可。

解密过程是难点：由于一个加密字符串可能对应多个原字符，直接枚举所有可能的解密结果会导致指数级复杂度。

优化策略：

预处理思想：既然dictionary是固定的，我们可以提前将dictionary中的每个单词加密，统计每种加密结果的出现次数
解密时：直接查表返回该加密字符串对应的dictionary单词数量

具体实现：

构造函数：建立char→string的加密映射，将所有dictionary单词加密并统计频次
encrypt函数：根据映射表逐字符加密
decrypt函数：直接查询预处理的频次表

这种方法将解密的复杂度从指数级降低到O(1)，是典型的"空间换时间"优化。

时间复杂度主要在预处理阶段，encrypt和decrypt都能快速响应。

代码实现

class Encrypter {
private:
    unordered_map<char, string> encryptMap;
    unordered_map<string, int> decryptCount;
    
public:
    Encrypter(vector<char>& keys, vector<string>& values, vector<string>& dictionary) {
        // 建立加密映射
        for (int i = 0; i < keys.size(); i++) {
            encryptMap[keys[i]] = values[i];
        }
        
        // 预处理：将dictionary中的每个单词加密并统计频次
        for (const string& word : dictionary) {
            string encrypted = encrypt(word);
            if (!encrypted.empty()) {
                decryptCount[encrypted]++;
            }
        }
    }
    
    string encrypt(string word1) {
        string result = "";
        for (char c : word1) {
            if (encryptMap.find(c) == encryptMap.end()) {
                return "";
            }
            result += encryptMap[c];
        }
        return result;
    }
    
    int decrypt(string word2) {
        return decryptCount[word2];
    }
};

class Encrypter:

    def __init__(self, keys: List[str], values: List[str], dictionary: List[str]):
        # 建立加密映射
        self.encrypt_map = {}
        for i in range(len(keys)):
            self.encrypt_map[keys[i]] = values[i]
        
        # 预处理：将dictionary中的每个单词加密并统计频次
        self.decrypt_count = {}
        for word in dictionary:
            encrypted = self.encrypt(word)
            if encrypted:
                self.decrypt_count[encrypted] = self.decrypt_count.get(encrypted, 0) + 1

    def encrypt(self, word1: str) -> str:
        result = []
        for c in word1:
            if c not in self.encrypt_map:
                return ""
            result.append(self.encrypt_map[c])
        return "".join(result)

    def decrypt(self, word2: str) -> int:
        return self.decrypt_count.get(word2, 0)

public class Encrypter {
    private Dictionary<char, string> encryptMap;
    private Dictionary<string, int> decryptCount;

    public Encrypter(char[] keys, string[] values, string[] dictionary) {
        // 建立加密映射
        encryptMap = new Dictionary<char, string>();
        for (int i = 0; i < keys.Length; i++) {
            encryptMap[keys[i]] = values[i];
        }
        
        // 预处理：将dictionary中的每个单词加密并统计频次
        decryptCount = new Dictionary<string, int>();
        foreach (string word in dictionary) {
            string encrypted = Encrypt(word);
            if (!string.IsNullOrEmpty(encrypted)) {
                if (decryptCount.ContainsKey(encrypted)) {
                    decryptCount[encrypted]++;
                } else {
                    decryptCount[encrypted] = 1;
                }
            }
        }
    }
    
    public string Encrypt(string word1) {
        StringBuilder result = new StringBuilder();
        foreach (char c in word1) {
            if (!encryptMap.ContainsKey(c)) {
                return "";
            }
            result.Append(encryptMap[c]);
        }
        return result.ToString();
    }
    
    public int Decrypt(string word2) {
        return decryptCount.GetValueOrDefault(word2, 0);
    }
}

var Encrypter = function(keys, values, dictionary) {
    // 建立加密映射
    this.encryptMap = new Map();
    for (let i = 0; i < keys.length; i++) {
        this.encryptMap.set(keys[i], values[i]);
    }
    
    // 预处理：将dictionary中的每个单词加密并统计频次
    this.decryptCount = new Map();
    for (const word of dictionary) {
        const encrypted = this.encrypt(word);
        if (encrypted) {
            this.decryptCount.set(encrypted, (this.decryptCount.get(encrypted) || 0) + 1);
        }
    }
};

Encrypter.prototype.encrypt = function(word1) {
    let result = "";
    for (const c of word1) {
        if (!this.encryptMap.has(c)) {
            return "";
        }
        result += this.encryptMap.get(c);
    }
    return result;
};

Encrypter.prototype.decrypt = function(word2) {
    return this.decryptCount.get(word2) || 0;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
构造函数	O(D×M)	O(K + D×M)
encrypt	O(N)	O(N)
decrypt	O(1)	O(1)

其中：

K：keys数组长度
D：dictionary数组长度
M：dictionary中单词的平均长度
N：待加密字符串长度

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目