## Monday, August 29, 2016

### [TopCoder]SRM 672 Div2 SubstitutionCipher

[TopCoder]SRM 672 Div2 SubstitutionCipher | 书影博客
Recently you learned about substitution ciphers. This problem is about such a cipher. All strings in this problem (both encrypted and decrypted ones) will consist of only uppercase English letters ('A'-'Z').
When encrypting text using a substitution cipher we choose a substitution table: a permutation p of the alphabet. In other words, for each letter x in the alphabet we choose a letter p(x) that will be used to encode x. This encoding must be one-to-one: if x and y are two different letters, the letters p(x) and p(y) chosen to encode them must also be different.
You decided to try it out: you chose some specific substitution table and used it to encrypt some strings.
At some later point in time you found an encrypted string y. You believe it was encrypted using the substitution table you once had. Sadly, you do not remember the substitution table anymore. The only thing you remember about it is that when you used it to encrypt the string a you got the string b. Is this information sufficient to decrypt y?
You are given the Strings a, b, and y. If it is possible to decrypt the string y, return the original string x that was encrypted into y. (More precisely: If there is exactly one string x such that the same permutation table can be used to encrypt a into b and to encrypt x into y, return x.) Otherwise, return an empty string.

def decode(self, a, b, y): letters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" s, t = set(letters), set(letters) letterMap = dict() for p, q in zip(a, b): z = letterMap.get(q) if not z: letterMap[q] = p s.remove(q) t.remove(p) elif z != p: return "" if len(s) == 1: letterMap[s.pop()] = t.pop() if set(letterMap) >= set(y): return "".join(map(letterMap.get, y)) return ""