题目描述：
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.
题目大意：
最近你了解了有关替换加密的知识。本题就是关于这种加密方法的。问题中的所有字符串（编码与解码字符串都是）只包含大写英文字母（'A' - 'Z'）。
当使用替换加密方法对文本进行加密时，我们选择一个替换表：字母表的排列p。换言之，字母表中的每一个字母x，都选择一个字母p(x)对其进行编码。这种编码肯定是一对一的：如果x和y是两种不同的字母，则用来编码的字母p(x)和p(y)也一定是不同的。
你决定亲自试一试：选择一个替换表并用它来编码字符串。
不久你找到一个编码之后的字符串y。你相信它是通过你所掌握的替换表编码得来的。遗憾的是，你不记得这个替换表是什么了。你唯一记得的是曾经将字符串a编得到字符串b。这样的信息足够对y解码吗？
给定字符串a, b和y。如果可以解码字符串y，则返回原始字符串x。（更加精确的表述：如果存在唯一的字符串x，应用与a编码b相同的替换表，可以编码得到y，则返回x）。否则，返回一个空字符串。
解题思路：
使用dict保存y中字母到x中字母的映射，从而重建替换表。
需要注意的地方：
存在x或者y中的去重字母数恰好等于25的情况，此时可以唯一确定26个字母中缺失的那一个，从而补全替换表。
Python代码：
class SubstitutionCipher(object):
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 ""
本文链接：http://bookshadow.com/weblog/2015/10/21/topcoder-srm-672-div2-substitution-cipher/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
