2227. Encrypt and Decrypt Strings

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.

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.

c++

struct Trie {
    Trie* next[26];
    bool eof = false;
    Trie() {memset(next,0,sizeof(next));}
    void insert(string& s, int p) {
        if(p == s.length()) eof = true;
        else {
            if(!next[s[p]-'a']) next[s[p]-'a'] = new Trie();
            next[s[p]-'a']->insert(s, p + 1);
        }
    }
};
class Encrypter {
    unordered_map<char, int> k;
    vector<string> v;
    unordered_map<string, unordered_set<char>> mpv;
    Trie* t, *rt;
public:
    Encrypter(vector<char>& keys, vector<string>& values, vector<string>& dictionary) {
        t = new Trie();
        rt = new Trie();
        v = values;

        for(int i = 0; i < keys.size(); i++)
            k[keys[i]] = i;
        for(int i = 0; i < values.size(); i++)
            mpv[values[i]].insert(keys[i]);
        for(auto& v : values)
            t->insert(v, 0);
        for(auto& d : dictionary) {
            auto rd = d;
            reverse(rd.begin(), rd.end());
            rt->insert(rd, 0);
        }
    }

    string encrypt(string word1) {
        stringstream ss;
        for(auto& w : word1) {
            ss<<v[k[w]];
        }
        return ss.str();
    }

    int decrypt(string word2) {
        auto [_, s] = helper(word2, 0);
        int res = 0;
        for(auto& rtrie : s) {
            res += rtrie->eof;
        }

        return res;
    }

    pair<bool,vector<Trie*>> helper(string& w, int p) {
        if(p == w.length()) return {true,{rt}};
        string ss;
        vector<Trie*> res;
        Trie* trie = t;
        bool PO = false;
        for(int i = p; i < w.length(); i++) {
            if(!trie->next[w[i]-'a']) break;

            trie = trie->next[w[i]-'a'];
            ss += w[i];
            if(!trie->eof) continue;
            auto [po, comb] = helper(w, i + 1);
            if(!po) continue;
            
            for(auto& rtrie : comb) {
                for(auto ch : mpv[ss]) {
                    if(!rtrie->next[ch-'a']) continue;
                    PO = true;
                    Trie* nrt = rtrie->next[ch-'a'];
                    res.push_back(nrt);
                }
            }
        }
        return {PO, res};
    }
};

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