如何解决"编程挑战(编程竞赛培训手册)"中提出的"密码踢球者"练习？

Question

"编程挑战(编程竞赛培训手册)"可能是关于算法的最好的练习册之一.我已经解决了前11个练习,但现在我遇到了"Crypt Kicker"问题:

Crypt Kicker
加密文本的一种常见但不安全的方法是置换字母表中的字母.换句话说,字母表中的每个字母在文本中始终被其他字母替换.为确保加密是可逆的,没有两个字母被相同的字母替换.

您的任务是解密几个编码的文本行,假设每行使用不同的替换集,并且解密文本中的所有单词都来自已知单词的字典.

输入
输入由一个包含整数n的行组成,后跟n个小写单词,每行一个,按字母顺序排列.这n个单词组成可能出现在解密文本中的单词字典.
字典后面有几行输入.如上所述加密每一行.

字典中的单词不超过1000个.没有字超过16个字母.加密行仅包含小写字母和空格,长度不超过80个字符.

输出
解密每一行并将其打印到标准输出.如果有多种解决方案,任何人都可以.
如果没有解决方案,请用星号替换字母表中的每个字母.

Sample Input 6
和
dick
jane
puff
spot
yertle

bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn
xxxx yyy zzzz www yyyy aaa bbbb ccc dddddd

样品输出
鸡巴和jane和粉扑和斑点和yertle ...

我应该采取什么策略来解决这个问题？我正在考虑一个经典而野蛮的回溯解决方案,但我正在努力避免这种情况,直到我发现更聪明的东西.

PS:这不是与家庭作业有关,我只是想提高我的整体技能.

Answer 1

KeyArray将保存替换表.

• 从空的KeyArray开始,这是版本0

• 将最长加密的单词与最长的字典单词匹配并添加到KeyArray(如果有两个最长,选择任何),这是版本1.

• 解密下一个最长的加密词的一些字母.

• 检查解密的字母是否与相同长度的任何字典单词中相同位置的字母匹配.
• 如果没有匹配,请返回版本0并尝试另一个单词.

• 如果某些字母匹配,则将其余字母添加到KeyArray,这是版本2.

• 解密下一个最长的加密词的一些字母.

• 检查解密的字母是否与任何字典单词中相同位置的字母匹配.
• 如果没有匹配,请返回版本1并尝试另一个单词
• 如果某些字母匹配,则将其余字母添加到KeyArray,这是版本3.

重复,直到所有单词都被解密.

如果在版本0,没有一个最长的单词在较短的单词中创建部分解密,很可能没有解决方案.