[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.
Read full article from [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.
使用dict保存y中字母到x中字母的映射，从而重建替换表。
需要注意的地方：
存在x或者y中的去重字母数恰好等于25的情况，此时可以唯一确定26个字母中缺失的那一个，从而补全替换表。
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 ""Read full article from [TopCoder]SRM 672 Div2 SubstitutionCipher | 书影博客
