14

“Programming Challenges (The Programming Contest Training Manual)”可能是最好的算法练习书之一。我已经解决了前 11 个练习，但现在我遇到了“Crypt Kicker”问题：

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

你的任务是解密几行编码的文本，假设每一行使用一组不同的替换，并且解密文本中的所有单词都来自已知单词的字典。

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

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

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

示例输入6
和
dick
jane
puff
spot
yertle

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

样本输出
dick and jane and puff and spot and yertle ...

我应该采取什么策略来解决这个问题？我正在考虑一个经典而残酷的回溯解决方案，但我试图避免这种情况，直到我找到更智能的东西。

PS：这与作业无关，我只是想提高我的整体技能。

4

5 回答 5

9

KeyArray 将保存替换表。

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

  • 将最长的加密词匹配到最长的字典词并添加到 KeyArray 中（如果有两个最长的，选择任何一个），这是版本 1。

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

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

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

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

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

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

如果在版本 0 中，最长的单词都没有在较短的单词中创建部分解密，那么很可能没有解决方案。

于 2010-02-01T09:44:02.937 回答
3

可以通过在回溯运行之前枚举可能性来进行较小的优化。在 Python 中：

dictionary = ['and', 'dick', 'jane', 'puff', 'spot', 'yertle']
line = ['bjvg', 'xsb', 'hxsn', 'xsb', 'qymm', 'xsb', 'rqat', 'xsb', 'pnetfn']

# ------------------------------------

import collections

words_of_length = collections.defaultdict(list)

for word in dictionary:
  words_of_length[len(word)].append(word)

possibilities = collections.defaultdict(set)
certainities = {}

for word in line:
    length = len(word)
    for i, letter in enumerate(word):
        if len(words_of_length[length]) == 1:
            match = words_of_length[length][0]
            certainities[letter] = match[i]
        else:
            for match in words_of_length[length]:
              possibilities[letter].add(match[i])

for letter in certainities.itervalues():
    for k in possibilities:
        possibilities[k].discard(letter)

for i, j in certainities.iteritems():
    possibilities[i] = set([j])

# ------------------------------------

import pprint
pprint.pprint(dict(possibilities))

输出：

{'a': set(['c', 'f', 'o']),
 'b': set(['d']),
 'e': set(['r']),
 'f': set(['l']),
 'g': set(['f', 'k']),
 'h': set(['j', 'p', 's']),
 'j': set(['i', 'p', 'u']),
 'm': set(['c', 'f', 'k', 'o']),
 'n': set(['e']),
 'p': set(['y']),
 'q': set(['i', 'j', 'p', 's', 'u']),
 'r': set(['j', 'p', 's']),
 's': set(['n']),
 't': set(['t']),
 'v': set(['c', 'f', 'o']),
 'x': set(['a']),
 'y': set(['i', 'p', 'u'])}

如果您有一些单一元素的可能性，您可以从输入中消除它们并重新运行算法。

编辑：切换到设置而不是列表并添加了打印代码。

于 2010-02-01T08:41:59.647 回答
2

我实际上尝试了一种完全不同的方法。我从字典单词中构建了一个 trie。然后我递归地遍历 trie 和句子（在 DFS 中遍历 trie）。

在每个空格处，我确保我在 trie 中找到了一个单词的结尾，如果是，我循环回到根。一路上，我一直在跟踪我到目前为止所做的字母分配。如果我有一个与先前分配相矛盾的分配，我会失败并将递归解开到可以进行下一个可能分配的程度。

这听起来很棘手，但似乎效果很好。而且编码真的没那么难！

于 2011-10-17T05:43:19.027 回答
0

另一种可能的优化，如果你有“足够”的文本来处理并且你知道文本的语言，你可以使用字母频率（见：）http://en.wikipedia.org/wiki/Letter_frequency。在处理 6 / 7 个单词时，这当然是一种非常近似的方法，但如果您有几页要解码，这将是最快的方法。

编辑：关于 Max 的解决方案，您也可以尝试提取单词的一些特征，例如重复字母。显然，指出字典中的 puff 和加密文本中的 qymm 是仅有的以双字母结尾的四个字母单词，可以直接回答其中 3 个字母。在更复杂的场景中，您应该能够缩小每个字母对的可能性。

于 2010-02-01T09:50:29.353 回答
-1

这是一个 Java 实现，对@Carlos Gutiérrez 提出的算法进行了更多改进。

Crypt Kicker 算法和解决方案，出了什么问题？

  • The refinement is to add a word pattern to reduce the search space for words. For example, words "abc" and "her" have the same pattern while "aac" and "her" don't as a three distinct letters word would not match a tow letters distinct word.

  • Moreover, the algorithm can be implemented recursively which is more intuitive and sensible.

于 2018-08-25T18:39:15.803 回答