Encrypt and Decrypt Strings

Problem

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.

Note that in case a character of the string is not present in keys, the encryption process cannot be carried out, and an empty string "" is returned.

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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18



    
    
    **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.

Solution

Method 1 – Trie and Backtracking for Decryption

Intuition

Encryption is a direct mapping from characters to values. Decryption is more complex: since multiple keys can map to the same value, we need to try all possible combinations. Using a trie for the dictionary allows efficient lookup and pruning during backtracking.

Approach

Build two maps:
- enc_map: char → value (for encryption)
- dec_map: value → list of chars (for decryption)
Build a trie from the dictionary for fast prefix search.
For encrypt(word1), for each char, append its value from enc_map. If any char is missing, return “”.
For decrypt(word2), use backtracking:
- At each position, try all possible chars for the current 2-letter substring using dec_map.
- Traverse the trie as you build the string. If you reach the end and the trie node is a word, count it.
- Return the total count.

Code

 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
41
42
43
44
45
46
47


class Trie {
public:
    Trie* next[26] = {};
    bool is_word = false;
};

class Encrypter {
    unordered_map<char, string> enc_map;
    unordered_map<string, vector<char>> dec_map;
    Trie* root;
public:
    Encrypter(vector<char>& keys, vector<string>& values, vector<string>& dictionary) {
        for (int i = 0; i < keys.size(); ++i) {
            enc_map[keys[i]] = values[i];
            dec_map[values[i]].push_back(keys[i]);
        }
        root = new Trie();
        for (auto& word : dictionary) {
            Trie* node = root;
            for (char c : word) {
                if (!node->next[c - 'a']) node->next[c - 'a'] = new Trie();
                node = node->next[c - 'a'];
            }
            node->is_word = true;
        }
    }
    string encrypt(string word1) {
        string ans;
        for (char c : word1) {
            if (!enc_map.count(c)) return "";
            ans += enc_map[c];
        }
        return ans;
    }
    int decrypt(string word2) {
        return dfs(word2, 0, root);
    }
    int dfs(const string& w, int i, Trie* node) {
        if (i == w.size()) return node->is_word;
        string s = w.substr(i, 2);
        int cnt = 0;
        for (char c : dec_map[s]) {
            if (node->next[c - 'a']) cnt += dfs(w, i + 2, node->next[c - 'a']);
        }
        return cnt;
    }
};

 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65


type Trie struct {
    next [26]*Trie
    isWord bool
}

type Encrypter struct {
    encMap map[byte]string
    decMap map[string][]byte
    root   *Trie
}

func Constructor(keys []byte, values []string, dictionary []string) Encrypter {
    encMap := map[byte]string{}
    decMap := map[string][]byte{}
    for i, k := range keys {
        encMap[k] = values[i]
        decMap[values[i]] = append(decMap[values[i]], k)
    }
    root := &Trie{}
    for _, word := range dictionary {
        node := root
        for i := 0; i < len(word); i++ {
            idx := word[i] - 'a'
            if node.next[idx] == nil {
                node.next[idx] = &Trie{}
            }
            node = node.next[idx]
        }
        node.isWord = true
    }
    return Encrypter{encMap, decMap, root}
}

func (e *Encrypter) Encrypt(word1 string) string {
    ans := ""
    for i := 0; i < len(word1); i++ {
        v, ok := e.encMap[word1[i]]
        if !ok {
            return ""
        }
        ans += v
    }
    return ans
}

func (e *Encrypter) Decrypt(word2 string) int {
    var dfs func(i int, node *Trie) int
    dfs = func(i int, node *Trie) int {
        if i == len(word2) {
            if node.isWord {
                return 1
            }
            return 0
        }
        s := word2[i : i+2]
        cnt := 0
        for _, c := range e.decMap[s] {
            if node.next[c-'a'] != nil {
                cnt += dfs(i+2, node.next[c-'a'])
            }
        }
        return cnt
    }
    return dfs(0, e.root)
}

 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
41
42
43


class Trie {
    Trie[] next = new Trie[26];
    boolean isWord = false;
}
class Encrypter {
    Map<Character, String> encMap = new HashMap<>();
    Map<String, List<Character>> decMap = new HashMap<>();
    Trie root = new Trie();
    public Encrypter(char[] keys, String[] values, String[] dictionary) {
        for (int i = 0; i < keys.length; ++i) {
            encMap.put(keys[i], values[i]);
            decMap.computeIfAbsent(values[i], k -> new ArrayList<>()).add(keys[i]);
        }
        for (String word : dictionary) {
            Trie node = root;
            for (char c : word.toCharArray()) {
                if (node.next[c - 'a'] == null) node.next[c - 'a'] = new Trie();
                node = node.next[c - 'a'];
            }
            node.isWord = true;
        }
    }
    public String encrypt(String word1) {
        StringBuilder ans = new StringBuilder();
        for (char c : word1.toCharArray()) {
            if (!encMap.containsKey(c)) return "";
            ans.append(encMap.get(c));
        }
        return ans.toString();
    }
    public int decrypt(String word2) {
        return dfs(word2, 0, root);
    }
    private int dfs(String w, int i, Trie node) {
        if (i == w.length()) return node.isWord ? 1 : 0;
        String s = w.substring(i, i+2);
        int cnt = 0;
        for (char c : decMap.getOrDefault(s, List.of())) {
            if (node.next[c - 'a'] != null) cnt += dfs(w, i+2, node.next[c - 'a']);
        }
        return cnt;
    }
}

 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


class Trie {
    val next = Array<Trie?>(26) { null }
    var isWord = false
}
class Encrypter(keys: CharArray, values: Array<String>, dictionary: Array<String>) {
    private val encMap = keys.zip(values).toMap()
    private val decMap = values.withIndex().groupBy({ it.value }, { keys[it.index] })
    private val root = Trie()
    init {
        for (word in dictionary) {
            var node = root
            for (c in word) {
                if (node.next[c - 'a'] == null) node.next[c - 'a'] = Trie()
                node = node.next[c - 'a']!!
            }
            node.isWord = true
        }
    }
    fun encrypt(word1: String): String {
        val ans = StringBuilder()
        for (c in word1) {
            val v = encMap[c] ?: return ""
            ans.append(v)
        }
        return ans.toString()
    }
    fun decrypt(word2: String): Int {
        fun dfs(i: Int, node: Trie): Int {
            if (i == word2.length) return if (node.isWord) 1 else 0
            val s = word2.substring(i, i+2)
            var cnt = 0
            for (c in decMap[s] ?: emptyList()) {
                node.next[c - 'a']?.let { cnt += dfs(i+2, it) }
            }
            return cnt
        }
        return dfs(0, root)
    }
}

 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


class Trie:
    def __init__(self):
        self.children = {}
        self.is_word = False

class Encrypter:
    def __init__(self, keys: list[str], values: list[str], dictionary: list[str]):
        self.enc_map = {k: v for k, v in zip(keys, values)}
        self.dec_map = {}
        for k, v in zip(keys, values):
            self.dec_map.setdefault(v, []).append(k)
        self.root = Trie()
        for word in dictionary:
            node = self.root
            for c in word:
                if c not in node.children:
                    node.children[c] = Trie()
                node = node.children[c]
            node.is_word = True
    def encrypt(self, word1: str) -> str:
        ans = []
        for c in word1:
            if c not in self.enc_map:
                return ""
            ans.append(self.enc_map[c])
        return ''.join(ans)
    def decrypt(self, word2: str) -> int:
        def dfs(i: int, node: Trie) -> int:
            if i == len(word2):
                return int(node.is_word)
            s = word2[i:i+2]
            cnt = 0
            for c in self.dec_map.get(s, []):
                if c in node.children:
                    cnt += dfs(i+2, node.children[c])
            return cnt
        return dfs(0, self.root)

 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69


use std::collections::HashMap;

struct Trie {
    next: [Option<Box<Trie>>; 26],
    is_word: bool,
}

impl Trie {
    fn new() -> Self {
        Self { next: Default::default(), is_word: false }
    }
}

struct Encrypter {
    enc_map: HashMap<char, String>,
    dec_map: HashMap<String, Vec<char>>,
    root: Box<Trie>,
}

impl Encrypter {
    fn new(keys: Vec<char>, values: Vec<String>, dictionary: Vec<String>) -> Self {
        let mut enc_map = HashMap::new();
        let mut dec_map = HashMap::new();
        for (k, v) in keys.iter().zip(values.iter()) {
            enc_map.insert(*k, v.clone());
            dec_map.entry(v.clone()).or_insert(vec![]).push(*k);
        }
        let mut root = Box::new(Trie::new());
        for word in dictionary.iter() {
            let mut node = &mut root;
            for c in word.chars() {
                let idx = (c as u8 - b'a') as usize;
                node = node.next[idx].get_or_insert_with(|| Box::new(Trie::new()));
            }
            node.is_word = true;
        }
        Self { enc_map, dec_map, root }
    }
    fn encrypt(&self, word1: String) -> String {
        let mut ans = String::new();
        for c in word1.chars() {
            if let Some(v) = self.enc_map.get(&c) {
                ans.push_str(v);
            } else {
                return String::new();
            }
        }
        ans
    }
    fn decrypt(&self, word2: String) -> i32 {
        fn dfs(i: usize, node: &Trie, word2: &str, dec_map: &HashMap<String, Vec<char>>) -> i32 {
            if i == word2.len() {
                return node.is_word as i32;
            }
            let s = &word2[i..i+2];
            let mut cnt = 0;
            if let Some(chars) = dec_map.get(s) {
                for &c in chars {
                    let idx = (c as u8 - b'a') as usize;
                    if let Some(child) = &node.next[idx] {
                        cnt += dfs(i+2, child, word2, dec_map);
                    }
                }
            }
            cnt
        }
        dfs(0, &self.root, &word2, &self.dec_map)
    }
}

 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
41
42
43
44
45
46
47


class Trie {
    next: Map<string, Trie> = new Map();
    isWord = false;
}
class Encrypter {
    private encMap: Map<string, string>;
    private decMap: Map<string, string[]>;
    private root: Trie;
    constructor(keys: string[], values: string[], dictionary: string[]) {
        this.encMap = new Map();
        this.decMap = new Map();
        for (let i = 0; i < keys.length; ++i) {
            this.encMap.set(keys[i], values[i]);
            if (!this.decMap.has(values[i])) this.decMap.set(values[i], []);
            this.decMap.get(values[i])!.push(keys[i]);
        }
        this.root = new Trie();
        for (const word of dictionary) {
            let node = this.root;
            for (const c of word) {
                if (!node.next.has(c)) node.next.set(c, new Trie());
                node = node.next.get(c)!;
            }
            node.isWord = true;
        }
    }
    encrypt(word1: string): string {
        let ans = "";
        for (const c of word1) {
            if (!this.encMap.has(c)) return "";
            ans += this.encMap.get(c);
        }
        return ans;
    }
    decrypt(word2: string): number {
        const dfs = (i: number, node: Trie): number => {
            if (i === word2.length) return node.isWord ? 1 : 0;
            const s = word2.substring(i, i+2);
            let cnt = 0;
            for (const c of this.decMap.get(s) ?? []) {
                if (node.next.has(c)) cnt += dfs(i+2, node.next.get(c)!);
            }
            return cnt;
        };
        return dfs(0, this.root);
    }
}

Complexity

⏰ Time complexity: O(L * 2^{L/2}) for decryption, where L is the length of the encrypted string. Encryption is O(M) for word length M.
🧺 Space complexity: O(N * K) for the trie, where N is the number of words in the dictionary and K is the average word length`.

Problem#

Examples#

Example 1#

Constraints#

Solution#

Method 1 – Trie and Backtracking for Decryption#

Intuition#

Approach#

Code#

Complexity#