python - 确定一个字符串是否可以由另一个字符串中的字符子集组成

Question

我有一个字典，其中字母对应于数字和一个字符串，如果每个字母在字符串中出现的次数等于或小于字典中与该字母关联的次数，则寻求返回 True。当这个问题不那么复杂并且没有出现次数的限制时，我使用了 all(x in string for x in dictionary)。是否有类似简洁的方法可以根据字典中的 int 值对此进行测试？

编辑:抱歉，这就是我们正在查看的内容。

def isValidWord(word, hand, wordList):
    """
    Returns True if word is in the wordList and is entirely
    composed of letters in the hand. Otherwise, returns False.

    Does not mutate hand or wordList.

    word: string
    hand: dictionary (string -> int)
    wordList: list of lowercase strings
    """
    if word.lower() in wordList and all(x in hand for x in word):
        return True
    else:
        return False

如果字符串中字母的任何实例显示为 Hand 的字典键，这段代码将返回 True，而我现在需要它返回 False，除非该字母出现的次数 <=该键的整数值。我已经相当困惑地完成了这项工作，并且想知道是否有一种方法可以将该级别的特异性合并到 all 方法或类似简洁的方法中。

Answer 1

从您的文档字符串中，您试图确定是否可以使用 hand 中的字母组成 word。使用 collections.Counter 非常简单。您甚至不需要制作 hand 字典。

def is_valid_word(word, hand, word_list):
    wc, hc = Counter(word), Counter(hand)
    return word.lower() in word_list and all(wc[k] <= hc[k] for k in wc)

如果你想将 hand 保留为字典，只需在最后一行使用 hand 而不是 hc 并省略将其转换为字典计数器。

就复杂性而言，这不是最优的，但可以使用相同的一般思想来编写一个好的算法。请注意，这比使用 count 更有效，因为每个字符串只需要迭代一次，而不是为每个唯一字母迭代一次。

检查这个的更有效的函数可能类似于:

def is_partial_anagram(word, pool):
    pool_counter = Counter(pool)
    for c in word:
        if not pool_counter[c]:
            return False
        pool_counter[c] -= 1
    return True

这里的复杂度是渐近相同的，但是当没有匹配时会更快地返回False并且避免为word构建一个Counter。