Formatted question description: https://leetcode.ca/all/2227.html

2227. Encrypt and Decrypt Strings (Hard)

You are given a character array keys containing unique characters and a string array values containing strings of length 2. You are also given another string array dictionary that contains all permitted original strings after decryption. You should implement a data structure that can encrypt or decrypt a 0-indexed string.

A string is encrypted with the following process:

For each character c in the string, we find the index i satisfying keys[i] == c in keys.
Replace c with values[i] in the string.

A string is decrypted with the following process:

For each substring s of length 2 occurring at an even index in the string, we find an i such that values[i] == s. If there are multiple valid i, we choose any one of them. This means a string could have multiple possible strings it can decrypt to.
Replace s with keys[i] in the string.

Implement the Encrypter class:

Encrypter(char[] keys, String[] values, String[] dictionary) Initializes the Encrypter class with keys, values, and dictionary.
String encrypt(String word1) Encrypts word1 with the encryption process described above and returns the encrypted string.
int decrypt(String word2) Returns the number of possible strings word2 could decrypt to that also appear in dictionary.

Example 1:

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

Explanation
Encrypter encrypter = new Encrypter([['a', 'b', 'c', 'd'], ["ei", "zf", "ei", "am"], ["abcd", "acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"]);
encrypter.encrypt("abcd"); // return "eizfeiam". 
                           // 'a' maps to "ei", 'b' maps to "zf", 'c' maps to "ei", and 'd' maps to "am".
encrypter.decrypt("eizfeiam"); // return 2. 
                              // "ei" can map to 'a' or 'c', "zf" maps to 'b', and "am" maps to 'd'. 
                              // Thus, the possible strings after decryption are "abad", "cbad", "abcd", and "cbcd". 
                              // 2 of those strings, "abad" and "abcd", appear in dictionary, so the answer is 2.

Constraints:

1 <= keys.length == values.length <= 26
values[i].length == 2
1 <= dictionary.length <= 100
1 <= dictionary[i].length <= 100
All keys[i] and dictionary[i] are unique.
1 <= word1.length <= 2000
1 <= word2.length <= 200
All word1[i] appear in keys.
word2.length is even.
keys, values[i], dictionary[i], word1, and word2 only contain lowercase English letters.
At most 200 calls will be made to encrypt and decrypt in total.

Companies:
Duolingo

Related Topics:
Hash Table, String

Similar Questions:

Solution 1. Hash Map

encrypt is straightforward. For decrypt, we can precompute ans store the frequencies of encrypted permitted original strings in a map freq, and return freq[word] in decrypt.

// OJ: https://leetcode.com/problems/encrypt-and-decrypt-strings/
// Time:
//      Encrypter: O(K + V + D) where `K` is the length of `keys`, `V` and `D` are the sizes of all the contents in `values` and `dict`, respectively.
//      encrypt: O(W) where `W` is the length of the input word
//      decrypt: O(W)
// Space: O(K + V + D)
class Encrypter {
    unordered_map<char, string> m; // mapping from character keys to corresponding value strings
    unordered_map<string, int> freq; // frequency map of encrypted permitted original strings
public:
    Encrypter(vector<char>& keys, vector<string>& values, vector<string>& dictionary) {
        for (int i = 0; i < keys.size(); ++i) {
            m[keys[i]] = values[i];
        }
        for (auto &s : dictionary) {
            auto e = encrypt(s);
            if (e.size()) freq[e]++;
        }
    }
    string encrypt(string s) {
        string ans;
        for (char c : s) {
            if (m.count(c) == 0) return ""; // invalid key character met, return empty string.
            ans += m[c];
        }
        return ans;
    }
    int decrypt(string s) {
        return freq.count(s) ? freq[s] : 0;
    }
};

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)

############

# 2227. Encrypt and Decrypt Strings
# https://leetcode.com/problems/encrypt-and-decrypt-strings

class Encrypter:

    def __init__(self, keys: List[str], values: List[str], dictionary: List[str]):
        self.ktov = {}
        
        for k, v in zip(keys, values):
            self.ktov[k] = v
        
        self.count = Counter(self.encrypt(x) for x in dictionary)
        

    def encrypt(self, word1: str) -> str:
        res = []
        
        for x in word1:
            if x in self.ktov:
                res.append(self.ktov[x])
            else:
                return ""
        
        return "".join(res)

    def decrypt(self, word2: str) -> int:
        return self.count[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);
 */

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

The problem didn’t say clearly whether a permitted original string might include unsupported keys. If it might include, then we need to consider the following testcase:

["Encrypter","decrypt"]
[[["a"],["pq"],["a","ax"]],["pq"]]

Discuss

https://leetcode.com/problems/encrypt-and-decrypt-strings/discuss/1908851

2227 - Encrypt and Decrypt Strings

2227. Encrypt and Decrypt Strings (Hard)

Solution 1. Hash Map

Discuss

All Problems

All Solutions

Welcome to Subscribe On Youtube

2227. Encrypt and Decrypt Strings (Hard)

Solution 1. Hash Map

Discuss

All Problems

All Solutions