leetcode
leetcode 1201 ~ 1250
加密解密字符串

加密解密字符串

难度:

标签:

题目描述

代码结果

运行时间: 138 ms, 内存: 21.3 MB


/*
思路:
1. 使用流来初始化 keyToValue 和 valueToKey 映射。
2. 使用流来实现 encrypt 方法,通过 map 操作将每个字符映射到对应的加密值。
3. 使用流来实现 decrypt 方法,通过过滤和计数操作来统计可以解密得到的原字符串。
*/
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

class Encrypter {
    private Map<Character, String> keyToValue;
    private Map<String, Character> valueToKey;
    private Set<String> dictionary;

    public Encrypter(char[] keys, String[] values, String[] dictionary) {
        keyToValue = IntStream.range(0, keys.length)
                .boxed()
                .collect(Collectors.toMap(i -> keys[i], i -> values[i]));
        valueToKey = IntStream.range(0, values.length)
                .boxed()
                .collect(Collectors.toMap(i -> values[i], i -> keys[i]));
        this.dictionary = Arrays.stream(dictionary).collect(Collectors.toSet());
    }

    public String encrypt(String word1) {
        return word1.chars()
                .mapToObj(c -> keyToValue.get((char) c))
                .collect(Collectors.joining());
    }

    public int decrypt(String word2) {
        return (int) dictionary.stream()
                .filter(original -> encrypt(original).equals(word2))
                .count();
    }
}

解释

方法:

这个解题思路包括了加密和解密两部分的实现。加密部分将每个字符映射到对应的字符串,并将这些字符串连接起来形成加密后的字符串。解密部分则是通过预计算字典中每个单词的加密结果,并存储这些结果出现的次数。解密时直接查找给定加密字符串在预计算结果中的次数。这样可以快速解密,而不需要每次都动态计算。

时间复杂度:

构造函数:O(n*m), encrypt函数:O(p), decrypt函数:O(1)

空间复杂度:

O(k + n)

代码细节讲解

🦆
在Encrypter类的构造函数中,为什么要预先计算字典中每个单词的加密结果并计数,这种方法的优势是什么?
预先计算字典中每个单词的加密结果并进行计数的做法主要是为了提高解密过程的效率。这种方式允许解密函数通过简单的哈希表查找,即可迅速得到一个加密字符串对应的所有可能原始单词的数量,而不需要重新对每个字典词条进行加密比较。这减少了重复的计算工作,特别是在字典较大或解密操作频繁的情况下,可以显著提高解密速度。
🦆
如果字典中的某些原始单词使用相同的keys序列加密后得到相同的字符串,解密函数如何处理这种情况?
如果多个原始单词加密后得到相同的字符串,解密函数会返回这些单词的总数。在Encrypter类的构造过程中,每个加密字符串对应的计数值会累加所有映射到该字符串的原始单词的数量。因此,解密时,返回的是加密字符串在预计算哈希表中的计数,这个计数反映了能够产生相同加密字符串的所有不同原始单词的总数。
🦆
在解密函数中使用哈希表查找,如果哈希表中不存在给定的加密字符串,该函数应该如何处理?
如果解密时给定的加密字符串在哈希表中不存在,这意味着没有任何字典中的单词在加密后可以生成这个字符串。在这种情况下,解密函数应返回0,表示不存在任何有效的原始单词映射到提供的加密字符串。
🦆
在加密映射创建过程中,如何处理values数组中存在重复字符串的情况?该如何确保加密的一致性和解密的正确性?
在创建加密映射时,如果values数组中存在重复的字符串,这可能会导致不同的keys映射到同一个value,从而在加密过程中导致信息的丢失或混淆。为确保加密的一致性和解密的正确性,最好避免这种设计。如果无法避免,应确保在解密时能够处理同一加密结果对应多个可能原始单词的情况。这通常意味着解密结果可能会返回多个潜在的匹配项的数量,而不是确切的单个原始单词。

相关问题