Может быть, я просто упускаю суть упражнения, но разве простое эвристическое правило не должно урезать большую часть поиска?Особенно, если вы пытаетесь просто найти одно слово, которое может вырезать наибольшее количество букв, вам, вероятно, просто захочется взглянуть на самые большие слова и проверить, не содержат ли они одно из самых маленьких.
Например,огромное количество слов включает буквы «а» и «я», которые являются действительными английскими словами.Более того, более длинные слова будут все чаще иметь одну или обе буквы.Вероятно, вы можете пропустить любое слово, которое не имеет «a» или «i» сразу.
Возможно, вы могли бы использовать это в решении Грега, на самом деле, если вы сначала получите свою отсортированную копию списка слов,то есть:
# Similar to Greg's. Reads into a dict
words = dict((x.strip(), None) for x in open("/usr/share/dict/words"))
# Generates a reverse sorted list from the dict (largest words first)
sortedwords = sorted(words, key=len, reverse=True)
# Largest possible reduction is making a longest word into 1 letter
longestPossible = len(sortedWords[0])-1
# Function that recursively finds shorter words and keeps count of reductions
def getMaxLettersRemoved(w, words, alreadyRemovedCount=0):
# If you've already calculated the value, return it
if words[w] is not None:
return words[w]
# Recursively calculate how many letters you can remove
shorterPossibilities = [w[:i] + w[i+1:] for i in xrange(len(w))]
# Calculate how max # of letters you can remove from shortened words
totalRemoved = max([getMaxLettersRemoved(w, words, alreadyRemovedCount+1) for shorter in shorterPossibilities if shorter in words])
# Total removed will be the same or will increase due to removals from shorter words
totalRemoved = max(totalRemoved, alreadyRemovedCount)
# Cache the result and return it
words[w] = totalRemoved
return totalRemoved
# Go through words from largest to smallest, so long as they have 'a' or 'i'
bestNumRemoved = 0
for w in sortedwords:
if 'a' in w or 'i' in w:
# Get the number of letters you can remove
numRemoved = getMaxLettersRemoved(w, words)
# Save the best one found
if numRemoved > bestNumRemoved:
bestWord = w
bestNumRemoved = numRemoved
# Stop if you can't do better
if bestNumRemoved >= len(w)-1:
break
# Need to make sure the best one found is better than any left
if bestNumRemoved < longestPossible:
for w in sortedwords:
# Get the number of letters you can remove
numRemoved = getMaxLettersRemoved(w, words)
# Save the best one found
if numRemoved > bestNumRemoved:
bestWord = w
bestNumRemoved = numRemoved
# Stop if you can't do better
if bestNumRemoved >= len(w)-2:
break
Так что это несколько отличается.Во-первых, он сортируется первым, чтобы вы могли получить самые большие слова.Во-вторых, он полностью игнорирует любое слово, не содержащее «a» или «i» при первом проходе.В-третьих, для получения результата не нужно вычислять каждое слово или все дерево.Вместо этого он просто рекурсивно просматривает слова по мере необходимости.
Каждый раз, когда он вырезает букву и находит новое слово, он запускает ту же функцию, чтобы узнать количество букв, которые он может вырезать из этого меньшего слова, плюс число, уже удаленное из любого корневого слова, которое онопришли из.Теоретически это должно быть достаточно быстрым, поскольку не нужно выполнять большинство слов, поскольку он выполняет типичный прием оптимизации: проверяет, находится ли он на оптимальной границе.Во-первых, он находит наилучшую возможность среди тех, у кого есть «я» или «а».Затем он проверяет слова длиннее найденного лучшего, чтобы убедиться, что нет лучшего варианта, который не содержит ни одной буквы, но длиннее как минимум на 2 буквы (так что теоретически это может быть лучше).
Вероятно, есть некоторые улучшения в этом, которые могли бы сделать еще лучшую работу, используя в своих интересах закономерности английского языка, используя вероятностный алгоритм, но я подозреваю, что это было бы хорошо как детерминистский.Кроме того, у меня нет под рукой словаря, так что я не могу на самом деле ... запустить его, но концепции верны.
Кроме того, я не совсем убежден, что сортировка спискаключи стоит того.Хотя алгоритм сортировки python работает довольно быстро, он все еще имеет дело с большим списком и может иметь довольно значительные затраты.Идеальный алгоритм, вероятно, должен был бы принять во внимание эту стоимость и решить, стоит ли это того или нет (вероятно, нет).Если вы не сортируете список, вы, вероятно, захотите, чтобы на первом проходе рассматривались только слова определенной минимальной длины, возможно, даже как часть большого цикла.В действительности нет никакого смысла вычислять что-либо, имеющее отношение к словам, которые могут не иметь ничего общего с решением.