如果有一个词,我怎么得到所有单词的列表,这些单词的区别是一个字母？

Question

假设我有"CAT"这个词.这些单词与"CAT"的区别在于一个字母(不是完整列表)

• 切
• 帽
• 拍
• 脂肪
• COT
• 等等

有一种优雅的方式来产生这个吗？显然,一种方法是通过蛮力.

pseduo代码:

while (0 to length of word)
    while (A to Z)
        replace one letter at a time, and check if the resulting word is a valid word

如果我有一个10个字母的单词,循环将运行26*10 = 260次.

有没有更好,更优雅的方式来做到这一点？

Answer 1

给出一个单词列表,例如

words = set(line.strip().lower() for line in open('/usr/share/dict/words'))

你可以构建和编写"通配"单词的索引,用通配符(比如"？")替换单词的每个字符,这样例如"gat"和"fat"都被索引为"？at":

def wildcard(s, idx):
    return s[:idx] + '?' + s[idx+1:]

def wildcarded(s):
    for idx in xrange(len(s)):
        yield wildcard(s, idx)

# list(wildcarded('cat')) returns ['?at', 'c?t', 'ca?']

from collections import defaultdict
index = defaultdict(list)

for word in words:
    for w in wildcarded(word):
        index[w].append(word)

现在,如果你想查找与"cat"相差一个字母的所有单词,只需查找"？at","c？t"和"ca？" 并连接结果:

def near_words(word):
    ret = []
    for w in wildcarded(word):
        ret += index[w]
    return ret

print near_words('cat')
# outputs ['cat', 'bat', 'zat', 'jat', 'kat', 'rat', 'sat', 'pat', 'hat', 'oat', 'gat', 'vat', 'nat', 'fat', 'lat', 'wat', 'eat', 'yat', 'mat', 'tat', 'cat', 'cut', 'cot', 'cit', 'cay', 'car', 'cap', 'caw', 'cat', 'can', 'cam', 'cal', 'cad', 'cab', 'cag']
print near_words('stack')
# outputs ['stack', 'stack', 'smack', 'spack', 'slack', 'snack', 'shack', 'swack', 'stuck', 'stack', 'stick', 'stock', 'stank', 'stack', 'stark', 'stauk', 'stalk', 'stack']

如果最大字长是L并且字数是N,则索引由O(NL)指针构成,而查找算法及时运行O(L + number of results).

如果你想要查找所有K字母不同的单词而不是1这种方法不能很好地概括,但这是一个非常难以完全普遍的问题(这是在汉明空间中找到邻居的问题).