{"id":9626,"date":"2022-04-03T02:39:44","date_gmt":"2022-04-03T09:39:44","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9626"},"modified":"2022-04-03T19:22:26","modified_gmt":"2022-04-04T02:22:26","slug":"leetcode-2227-encrypt-and-decrypt-strings","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/data-structure\/leetcode-2227-encrypt-and-decrypt-strings\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2227. Encrypt and Decrypt Strings"},"content":{"rendered":"\n

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

A string is encrypted<\/strong> with the following process:<\/p>\n\n\n\n

  1. For each character c<\/code> in the string, we find the index i<\/code> satisfying keys[i] == c<\/code> in keys<\/code>.<\/li>
  2. Replace c<\/code> with values[i]<\/code> in the string.<\/li><\/ol>\n\n\n\n

    A string is decrypted<\/strong> with the following process:<\/p>\n\n\n\n

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

      Implement the Encrypter<\/code> class:<\/p>\n\n\n\n

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

        Example 1:<\/strong><\/p>\n\n\n\n

        Input<\/strong>\n[\"Encrypter\", \"encrypt\", \"decrypt\"]\n[[['a', 'b', 'c', 'd'], [\"ei\", \"zf\", \"ei\", \"am\"], [\"abcd\", \"acbd\", \"adbc\", \"badc\", \"dacb\", \"cadb\", \"cbda\", \"abad\"]], [\"abcd\"], [\"eizfeiam\"]]\nOutput<\/strong>\n<\/pre>\n\n\n
        [null, “eizfeiam”, 2]<\/p>\n\n\n\n
        Explanation<\/strong> 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.<\/p>\n\n\n\n
        Constraints:<\/strong><\/p>\n\n\n\n
        • 1 <= keys.length == values.length <= 26<\/code><\/li>
        • values[i].length == 2<\/code><\/li>
        • 1 <= dictionary.length <= 100<\/code><\/li>
        • 1 <= dictionary[i].length <= 100<\/code><\/li>
        • All keys[i]<\/code> and dictionary[i]<\/code> are unique<\/strong>.<\/li>
        • 1 <= word1.length <= 2000<\/code><\/li>
        • 1 <= word2.length <= 200<\/code><\/li>
        • All word1[i]<\/code> appear in keys<\/code>.<\/li>
        • word2.length<\/code> is even.<\/li>
        • keys<\/code>, values[i]<\/code>, dictionary[i]<\/code>, word1<\/code>, and word2<\/code> only contain lowercase English letters.<\/li>
        • At most 200<\/code> calls will be made to encrypt<\/code> and decrypt<\/code> in total<\/strong>.<\/li><\/ul>\n\n\n\n
          Solution: <\/strong><\/h2>\n\n\n\n
          For encryption, follow the instruction. Time complexity: O(len(word)) = O(2000)
          For decryption, try all words in the dictionary and encrypt them and compare the encrypted string with the word to decrypt. Time complexity: O(sum(len(word_in_dict))) = O(100*100)<\/p>\n\n\n\n
          Worst case: 200 calls to decryption, T = 200 * O(100 * 100) = O(2*106<\/sup>)<\/p>\n\n\n\n
          \n
          C++<\/h2>\n
          \n\n
          \n\/\/ Author: Huahua\nclass Encrypter {\npublic:\n  Encrypter(vector& keys, \n            vector& values, \n            vector& dictionary):\n        vals(26),\n        dict(dictionary) {\n    for (size_t i = 0; i < keys.size(); ++i)\n      vals[keys[i] - 'a'] = values[i];  \n  }\n\n  string encrypt(string word1) {\n    string ans;\n    for (char c : word1)\n      ans += vals[c - 'a'];\n    return ans;\n  }\n\n  int decrypt(string word2) {\n    return count_if(begin(dict), end(dict), [&](const string& w){ \n      return encrypt(w) == word2;\n    });    \n  }\nprivate:\n  vector vals;\n  vector dict;\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
          Optimization<\/strong><\/h2>\n\n\n\n
          Pre-compute answer for all the words in dictionary.<\/p>\n\n\n\n
          decrypt: Time complexity: O(1)<\/p>\n\n\n\n
          \n
          C++<\/h2>\n
          \n\n
          \n\/\/ Author: Huahua\nclass Encrypter {\npublic:\n  Encrypter(vector& keys, \n            vector& values, \n            vector& dictionary):\n        vals(26) {\n    for (size_t i = 0; i < keys.size(); ++i)\n      vals[keys[i] - 'a'] = values[i];  \n    for (const string& w : dictionary)\n      ++counts[encrypt(w)];\n  }\n\n  string encrypt(string word1) {\n    string ans;\n    for (char c : word1)\n      ans += vals[c - 'a'];\n    return ans;\n  }\n\n  int decrypt(string word2) {\n    auto it = counts.find(word2);\n    return it == counts.end() ? 0 : it->second;\n  }\nprivate:\n  vector vals;  \n  unordered_map counts;\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
          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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[89],"tags":[291,773,217,4],"class_list":["post-9626","post","type-post","status-publish","format-standard","hentry","category-data-structure","tag-data-structure","tag-dictionary","tag-hard","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9626","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=9626"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9626\/revisions"}],"predecessor-version":[{"id":9631,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9626\/revisions\/9631"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9626"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9626"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9626"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}