-1

我想找到最有效的方法来遍历在 Python 中输入的字母组合并返回一组单词，其组合包括所有字母（如果可行）。

例子：

假设用户输入了 ABCD E。目标是找到包含所有字母的最少单词数。在这种情况下，按优先顺序排列的最佳解决方案将是：

  1. 一个包含所有 5 个字母的单词
  2. 两个包含所有 5 个字母的单词。（可以是 4 字母词 + 1 字母词或 3 字母词 + 2 字母词。没有区别）

.... ETC。

如果不匹配，则查找返回 1。带有 n-1 个字母等。

我有一个功能来检查“字母组合”（即单词）是否在字典中。

def is_in_lib(word):
    if word in lib:
        return word
    return False

理想的答案不应该包括找到这些字母的组合并搜索所有这些字母。搜索我的字典非常昂贵，所以我需要一些可以优化我们搜索字典的时间的东西

重要编辑：订单很重要，需要连续性。这意味着如果用户输入“H”、“T”、“A”，则无法构建“HAT”。

真实例子：如果输入是：T - H - G - R - A - C - E - K - B - Y - E "输出应该是 "Grace" 和 "Bye"

4

2 回答 2

0

我认为这里的关键思想是有某种索引提供从规范的字符序列到实际单词的映射。像这样的东西：

# List of known words
>>> words = ('bonjour', 'jour', 'bon', 'poire', 'proie')


# Build the index
>>> index = collections.defaultdict(list)
>>> for w in words:
...     index[''.join(sorted(w.lower()))].append(w)
...

这将产生一种有效的方法来查找与字符序列相对应的所有字谜：

>>> index
defaultdict(<class 'list'>, {'joru': ['jour'], 'eiopr': ['poire', 'proie'], 'bjnooru': ['bonjour'], 'bno': ['bon']})

您可以这样查询索引：

>>> user_str = 'OIREP'
>>> index.get(''.join(sorted(user_str.lower())), "")
['poire', 'proie']

当然，这只会找到“精确”的字谜——即包含用户提供的所有字母。要查找与用户提供的字符串的子集匹配的所有字符串，您必须一次删除一个字母并再次检查每个组合。我觉得递归将有助于解决这个问题；）

编辑：（ 我应该把它放在剧透部分吗？）

这是一个可能的解决方案：

import collections

words = ('bonjour', 'jour', 'bon', 'or', 'pire', 'poire', 'proie')

index = collections.defaultdict(list)
for w in words:
    index[''.join(sorted(w.lower()))].append(w)

# Recursively search all the words containing a sequence of letters
def search(letters, result = set()):
    # Assume "letters" ordered
    if not letters:
        return

    solutions = index.get(letters)
    if solutions:
        for s in solutions:
            result.add(s)

    for i in range(0,len(letters)):
        search(letters[:i]+letters[i+1:], result)

    return result


# Use case:
user_str = "OIREP"

s = search(''.join(sorted(user_str.lower())))
print(s)

生产：

set(['poire', 'or', 'proie', 'pire'])

它不是那么糟糕，但可以改进，因为相同的字符子集被检查了几次。当用户提供的搜索字符串包含多个相同的字母时尤其如此。

于 2013-06-16T15:22:22.487 回答
0

您可以从输入字母创建一个字符串/列表，并在词库中的每个单词上迭代它们：

    inputstring='abcde'
    for i in lib:
            is_okay=True
            for j in inputstring:
                    if i.find(j)=-1:
                            is_okay=False
            if is_okay:
                    return i

我认为其他情况（两个单词，3-2个字母）可以递归实现，但效率不高。

于 2013-06-16T15:27:33.417 回答