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:

1. For each character c in the string, we find the index i satisfying keys[i] == c in keys.
2. 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:

1. 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.
2. 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

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

1. Build two maps:
   • enc_map: char → value (for encryption)
   • dec_map: value → list of chars (for decryption)
2. Build a trie from the dictionary for fast prefix search.
3. For encrypt(word1), for each char, append its value from enc_map. If any char is missing, return "".
4. 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

C++

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;
    }
};

Go

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)
}

Java

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;
    }
}

Kotlin

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)
    }
}

Python

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)

Rust

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)
    }
}

TypeScript

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