PYTHON- 给定一个起始单词，哪种字母组合可以最大化拼写有效单词的数量

Question

编辑：新问题。因为我怀疑这个问题比我最开始想的要复杂，可能是NP难度，所以我有了另一个问题：有什么有用的算法可以接近最大化使用字母的数量吗？

我受到了一款叫Scrabble Slam!的纸牌游戏的启发，想写一个程序。不过我对算法还不太熟悉，想不出一个高效的解决办法：

你从一个包含有效的四个字母的英文单词的字符串开始。你可以一次放一个字母在这个单词上，通过放这个字母形成一个新的字典中有效的单词。你手里的字母和字母表中的字母是一样的。

举个例子，如果起始单词是“cart”，那么可以有这样一个有效的操作序列：

sand --> sane --> sine --> line --> lins --> pins --> fins，等等。

目标是通过使用尽可能多的字母（每个字母不能用超过一次），来最大化序列中的单词数量。

我的算法不能找到最长的序列，只能猜测最长的可能是什么。

首先，它会列出所有可以通过改变起始单词一个字母形成的单词。这个列表叫做“adjacentList”。然后，它会查看adjacentList中的所有单词，找出哪些单词有最多的相邻单词。选择相邻单词最多的那个单词，将起始单词转换为它。

例如，单词sane可以变成28个其他单词，单词sine可以变成27个其他单词，单词line可以变成30个其他单词——每一个选择都是为了最大化拼出更多单词的可能性。

解决这个问题的最佳方法是什么？什么样的数据结构最优？我该如何改进我的代码，使其更高效且不那么冗长？

##Returns a list of all adjacent words.  Lists contain tuples of the adjacent word and the letter that
##makes the difference between those two words.

def adjacentWords(userWord):
    adjacentList, exactMatches, wrongMatches = list(), list(), str()
    for dictWords in allWords:
        for a,b in zip(userWord, dictWords):
            if a==b: exactMatches.append(a)
            else: wrongMatches = b
        if len(exactMatches) == 3:
            adjacentList.append((dictWords, wrongMatches))
        exactMatches, wrongMatches = list(), list()
    return adjacentList
    #return [dictWords for dictWords in allWords if len([0 for a,b in zip(userWord, dictWords) if a==b]) == 3]


def adjacentLength(content):
    return (len(adjacentWords(content[0])), content[0], content[1])

#Find a word that can be turned into the most other words by changing one letter
def maxLength(adjacentList, startingLetters):
    return max(adjacentLength(content) for content in adjacentList if content[1] in startingLetters)

def main():
    startingWord = "sand"
    startingLetters = "a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z".replace(" ", "").split(',')

    existingWords = list()
    while True:
        adjacentList = adjacentWords(startingWord)
        letterChoice = maxLength(adjacentList, startingLetters)
        if letterChoice[1] not in existingWords:
            print "Going to use letter: "+ str(letterChoice[2]) + " to spell the word "+ str(letterChoice[1]) + " with "+ str(letterChoice[0]) + " possibilities."
            existingWords.append(letterChoice[1])
            startingLetters.remove(str(letterChoice[2]))
            startingWord = letterChoice[1]


main()

数据结构字典查找算法最优化有效单词字母组合 NP难度单词序列

PYTHON- 给定一个起始单词，哪种字母组合可以最大化拼写有效单词的数量

2 个回答

撰写回答