0

我在这个页面上遇到了这个面试问题：（http://newworld-alex.blogspot.com/2009/03/facebook-interviewzz.html）

技术问题：在 python 中，给定某个单词的字符变体字典，例如 dictChars = {"e" : [E, 3], "x" : [X], "a" : [A, @], "m " : [M]}实现一个类似密码破解器的部分字符串置换生成器，即产生exaM, exAm, exAM, ex@m, ...。我在 Python 中实现了一个简单的 3 行递归解决方案。

我在 Python 中有一个解决方案，但我似乎不知道如何像他那样让它变成 3 行。

仅供参考，这是我目前的解决方案：

def allPossiblePasswords(password, mapping):
   if len(password) == 0:
      return [""]
   else:
      next = allPossiblePasswords(password[1:], mapping)
      if password[0] in mapping:
         return [c + n for c in mapping[password[0]] for n in next]
      else:
         return [password[0] + n for n in next]

提前致谢！

4

4 回答 4

3

自我剽窃不算数，对吧？

import itertools

def all_possibles(password, mapping):
    char_options = ([char]+mapping.get(char,[]) for char in password)
    for poss in itertools.product(*char_options):
        yield ''.join(poss)

可以根据需要制作得尽可能紧凑，甚至是单行变体：

possibles = lambda p,m: map(''.join, itertools.product(*([c]+m.get(c,[]) for c in p)))

编辑：啊。我没有注意到递归是必需的。在这种情况下，如何：

def all_recur(password, mapping):
    return [''] if not password else [c + n for c in [password[0]] + mapping.get(password[0], []) for n in all_recur(password[1:], mapping)]

这基本上只是你的压缩版本。请注意，这两个都返回“exam”（即未修改的密码）；我不确定这是不是想要的。

于 2012-04-10T01:57:47.013 回答
1 
mapping = {'a': ['A', '@'], 'x': ['X'], 'e': ['E', 3], 'm': ['M']}

password = "exam"

from itertools import product
allPossible = list(product(*([letter] + mapping[letter] for letter in password)))
于 2012-04-10T01:55:50.007 回答
1

这在很多方面都是错误的。但无论如何我都会发布它。根据要求，这是一个递归解决方案。

>>> def pw_vars(in_word, out_word, equivs):
...     if not in_word: return [out_word]
...     return sum((pw_vars(in_word[1:], out_word + c, equivs) for c in [in_word[0]] + equivs[in_word[0]]), [])
... 
>>> pw_vars('foo', '', {'f':['F', '='], 'o':['0', 'O']})
['foo', 'fo0', 'foO', 'f0o', 'f00', 'f0O', 'fOo', 'fO0', 'fOO', 'Foo', 'Fo0', 
 'FoO', 'F0o', 'F00', 'F0O', 'FOo', 'FO0', 'FOO', '=oo', '=o0', '=oO', '=0o', 
 '=00', '=0O', '=Oo', '=O0', '=OO']

我希望我不必说你永远不应该这样做。这个人真的得到了这份工作吗？我很怀疑。

实际上，虽然我已经意识到 DSM 的版本更好——几乎可以忍受！这是我的 DSM 版本，它的价值（不是那么多）。这也满足了 Mark Ransom 下面的观点。

>>> def pw_vars(pw, equivs):
...     if not pw: return ('',)
...     return (c + var for c in [pw[0]] + equivs.get(pw[0]) for var in pw_vars(pw[1:], equivs))
... 
>>> list(pw_vars('foo', {'f':['F', '='], 'o':['0', 'O']}))
['foo', 'fo0', 'foO', 'f0o', 'f00', 'f0O', 'fOo', 'fO0', 'fOO', 'Foo', 'Fo0', 'FoO', 'F0o', 'F00', 'F0O', 'FOo', 'FO0', 'FOO', '=oo', '=o0', '=oO', '=0o', '=00', '=0O', '=Oo', '=O0', '=OO']
于 2012-04-10T02:15:07.973 回答
0 
equivs = dict(e=['E', '3'], x=['X'], a=['A', '@'], m=['M'])

def gen(c, *cs):
    if cs: return (x + y for x in [c] + equivs.get(c, []) for y in gen(*cs))
    else: return [c] + equivs.get(c, [])

for each in gen(*'erxuam'):
    print each
于 2012-04-10T05:00:39.233 回答