一尘不染

如何解决“编程挑战(编程竞赛培训手册)”中提出的“地穴突击手”练习?

algorithm

“编程挑战(编程竞赛培训手册)”可能是关于算法的最好的练习书之一。我已经解决了前11个练习,但现在遇到了“地穴踢球”问题:

地穴踢球者
加密文本的一种常见但不安全的方法是置换字母。换句话说,字母表中的每个字母在文本中始终被其他字母替换。为确保加密是可逆的,同一字母不会替换两个字母。

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

输入
输入包含一行,该行包含一个整数n,后跟n个小写单词,每行一个,按字母顺序排列。这n个单词构成了可能出现在解密文本中的单词词典。
在字典之后是几行输入。每行如上所述进行加密。

词典中的单词数不超过1,000。没有一个单词超过16个字母。加密的行仅包含小写字母和空格,并且长度不超过80个字符。

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

样品输入 6

迪克

粉扑

yertle

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

样本输出
鸡巴和简和粉扑以及斑点和斑点…

为了解决此问题,我应该采取什么 策略 ?我当时在考虑一种经典而残酷的回溯解决方案,但是在我发现更明智的方法之前,我一直在努力避免这种情况。

PS:这与家庭作业无关,我只是想提高自己的整体技能。


阅读 261

收藏
2020-07-28

共1个答案

一尘不染

KeyArray将保存替换表。

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

  • 将最长的加密单词与最长的字典单词匹配,然后添加到KeyArray(如果有两个最长的单词,则选择任意一个),这是版本1。

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

  • 检查解密的字母是否与相同长度的任何字典单词中相同位置的字母匹配。

  • 如果没有匹配项,请返回版本0并尝试另一个单词。
  • 如果某些字母匹配,则将其余字母添加到KeyArray,这是版本2。

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

  • 检查解密的字母是否与任何词典单词中相同位置的字母匹配。

  • 如果没有匹配项,请返回到版本1并尝试另一个单词
  • 如果某些字母匹配,则将其余字母添加到KeyArray,这是版本3。

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

如果在版本0中,最长的字都没有创建较短字的部分解密,则很可能没有解决方案。

2020-07-28