跳转至

2227. 加密解密字符串

题目描述

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

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

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

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

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

  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 次

解法

方法一：哈希表

我们用一个哈希表 \(\textit{mp}\) 记录每个字符的加密结果，用另一个哈希表 \(\textit{cnt}\) 记录每个加密结果出现的次数。

在构造函数中，我们遍历 \(\textit{keys}\) 和 \(\textit{values}\)，将每个字符和其对应的加密结果存入 \(\textit{mp}\) 中。然后遍历 \(\textit{dictionary}\)，统计每个加密结果出现的次数。时间复杂度 \((n + m)\)，其中 \(n\) 和 \(m\) 分别是 \(\textit{keys}\) 和 \(\textit{dictionary}\) 的长度。

在加密函数中，我们遍历输入字符串 \(\textit{word1}\) 的每个字符，查找其加密结果并拼接起来。如果某个字符没有对应的加密结果，说明无法加密，返回空字符串。时间复杂度 \(O(k)\)，其中 \(k\) 是 \(\textit{word1}\) 的长度。

在解密函数中，我们直接返回 \(\textit{cnt}\) 中 \(\textit{word2}\) 对应的次数。时间复杂度 \(O(1)\)。

空间复杂度 \(O(n + m)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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) {
            cnt.merge(encrypt(w), 1, Integer::sum);
        }
    }

    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);
 */

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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);
 */

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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);
 */

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Encrypter {
    private mp: Map<string, string> = new Map();
    private cnt: Map<string, number> = new Map();

    constructor(keys: string[], values: string[], dictionary: string[]) {
        for (let i = 0; i < keys.length; i++) {
            this.mp.set(keys[i], values[i]);
        }
        for (const w of dictionary) {
            const encrypted = this.encrypt(w);
            if (encrypted !== '') {
                this.cnt.set(encrypted, (this.cnt.get(encrypted) || 0) + 1);
            }
        }
    }

    encrypt(word: string): string {
        let res = '';
        for (const c of word) {
            if (!this.mp.has(c)) {
                return '';
            }
            res += this.mp.get(c);
        }
        return res;
    }

    decrypt(word: string): number {
        return this.cnt.get(word) || 0;
    }
}

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

评论