Substitution Cipher Dictionary Matcher
Remitly● MediumFULLTIMEONSITE INTERVIEWProblem statement
A substitution cipher maps every occurrence of one letter to the same other letter, and different source letters must map to different target letters. Two equal-length words therefore match when their characters have the same repetition pattern.
Given an immutable dictionary and an ordered array of queries, return one match list per query. Keep matching dictionary entries in their original order and preserve duplicates. The outer result follows query order.
Preprocess the dictionary once so repeated queries do not rescan every word.
Function
findCipherMatches(dictionary: String[], queries: String[]) → String[][]Examples
Example 1
dictionary = ["foo","bar","paper","title","egg","add","noon"]queries = ["abb","kick","xyyx"]return = [["foo","egg","add"],[],["noon"]]abb has the pattern first-second-second, while xyyx has the pattern first-second-second-first. No four-letter dictionary word matches kick.
Example 2
dictionary = ["paper","title","apple"]queries = ["radar","level"]return = [[],[]]paper and title have pattern 0,1,0,2,3, while both radar and level have pattern 0,1,2,1,0. Therefore neither query has a match.
Example 3
dictionary = ["ab","cd","ab","aa"]queries = ["xy","zz"]return = [["ab","cd","ab"],["aa"]]Original dictionary order and duplicate entries are preserved in each match list.
Constraints
0 <= dictionary.length <= 200000 <= queries.length <= 20001 <= dictionary[i].length, queries[i].length <= 50- Every word contains only lowercase English letters.