Substitution Cipher Dictionary Matcher
Learn this problem
RemitlyFULLTIMEONSITE INTERVIEWProblem statement
A substitution cipher replaces every occurrence of one letter with the same other letter, and two different source letters cannot map to the same target letter. Therefore, two equal-length words match when their characters have the same repetition pattern.
Given an immutable dictionary and an ordered batch of query words, return one match list for each query. A dictionary word matches a query when the two words are isomorphic under a position-preserving bijection between their lowercase letters.
Keep matches in their original dictionary order, and preserve duplicate dictionary entries. The outer result follows query order.
Your implementation should preprocess the dictionary once so repeated queries do not rescan every dictionary 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","title"],["paper","title"]]Both queries and the first two dictionary words have the same five-position repetition pattern.
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.