步骤字字谜 python

Question

通过取一个给定的单词，添加一个字母，然后对结果进行拼写来形成一个步骤单词。例如，以单词“APPLE”开头，可以添加“A”和字谜得到“APPEAL”。给定一个全局单词字典，创建一个函数 step(word)，它返回字典中出现的所有唯一的、有效的步骤单词的列表。字典：https : //raw.githubusercontent.com/eneko/data-repository/master/data/words.txt我使用以下链接制作了一本字典：>>> words = open('words.txt', encoding='ascii').read().upper().split()此分配应在没有任何其他库函数调用的情况下完成。有几种解决方案，但有些比其他的更好更快。您如何加快解决方案的速度？解决方案应如下所示。>>> step("APPLE")>>>['APPEAL', 'CAPPLE', 'PALPED', 'LAPPED', 'DAPPLE', 'ALEPPO', 'LAPPER', 'RAPPEL', 'LAPPET', 'PAPULE', 'UPLEAP']

Answer 1

正如我们所知，排序形式的字谜是完全相同的。

逻辑：

1. 创建一个用于查找的字典。其中键将是排序字符串，值将是键的字谜数组。

2. 将所有字母 (A..Z) 一个一个地添加到输入字符串中，一次一个，这样结果字符串包含一个比输入字符串多一个字母并且是排序的形式。现在，在上一步创建的字典中找到字谜。

3. 您从步骤 2 中获得的所有值的组合将是您的预期输出。

谈论运行时代码的复杂性。（不包括创建常量（如用于查找的字典、字母表）的时间）

需要 O(NxLogN) + O(26xN) ~ O(NxLogN)

• 26：字母数

• N：输入字符串的长度

1. 要排序的输入字符串一旦该sorted功能需要NlogN的时间在最坏的情况下。

2. 要创建新的排序字符串添加一个字母来排序的输入字符串需要26xN时间。

代码：

# array of all valid and unique words from the dictionary

valid_words = set(open('words.txt', encoding='ascii').read().upper().split())

look_up = {}

for word in valid_words:

  try:

    look_up[''.join(sorted(word))].append(word)

  except KeyError:

    look_up[''.join(sorted(word))] = [word]

alphabet_array = []

alphabet_dict = {}

for i in range (65, 91):

  alphabet_dict[chr(i)]=i

  alphabet_array.append(chr(i))

def step(word):

  sorted_string = sorted(word)

  length_of_input_string = len(sorted_string)

  output_values = []

  for i in alphabet_array:

    new_str = ''

    value_added = 0

    for j in range (0, length_of_input_string):

      if value_added==0 and (alphabet_dict[sorted_string[j]] > alphabet_dict[i]):

        new_str += i

        value_added = 1

      new_str += sorted_string[j]

    if value_added==0:

      new_str += i

    try:

      output_values+=look_up[new_str]

    except KeyError:

      pass

  return output_values

if __name__ == '__main__':

  input_string = 'APPLE'

  print (step(input_string))

Answer 2

由于字谜具有相同的字母，如果您按字母顺序对单词中的字母进行排序，对于互为字谜的单词，您将得到相同的字符串。例如：LEAP -> 按字母顺序排序 -> AEPL PALE -> 按字母顺序排序 -> AEPL

1) 您应该遍历字典中的所有单词，并创建按字母顺序排序的字符串键查找具有相同键的单词列表。

给定一个单词列表

["PALE","LEAP"]

你会得到如下的字谜查找

{

"AEPL"=>["PALE","LEAP"],

...

} 

2）接下来，取输入的单词，尝试不同的字母组合来创建一个新的字符串。对此字符串进行排序并根据字谜字典查找匹配项。将返回的列表连接成一个列表并返回该列表。

假设输入词是 PEA，生成所有组合

["PEAA","PEAB"...,"PEAL",...]

按字母顺序排列每个候选词

["AAEP","ABEP",...,"AEPL",...]

然后查找并连接返回的列表

["LEAP","PALE"]

如果您也想要这里的 Python 代码，请告诉我，但是编写代码应该很容易。加速主要是由于对字谜查找字典进行了预处理，因此最终查找在接近恒定的时间内运行，但它使用了输入列表中单词顺序的额外空间。

Answer 3

请看下面的实现和解释： 对于这个问题，我们可以把它分成两部分：首先尝试建立一个词图，defaultdict用于将所有相似的字谜词存储到列表中。例如，具有相同字母的单词，如 TEA、EAT，应该具有相同的键。

创建单词图将使我们能够遍历 N 个单词并对它们进行排序。运行时间将为 O(N * k logk) - 假设平均字长为 k。

其次，我们可以遍历每个字母并将其添加到给定的单词中，并检查该键的新值是否已经在映射中。如果是这样，我们找到步骤词并将其添加到结果中。

from collections import defaultdict

from string import ascii_uppercase as uppers

def make_wordmap(dictionary):   # first part - build up the lookup hash map

    maps = defaultdict(list)

    for word in dictionary:

        maps[tuple(sorted(word))].append(word)

    return maps

def step_words(word, dc):              # search the word from dict by using the maps

    word_map =  make_wordmap(dc)

    step_words = []

    for letter in uppers:

        key = tuple(sorted(word + letter))

        if word_map[key]:

            step_words.extend(word_map[key])

    return step_words

if __name__ == '__main__':

    dictionary = ['APPEAL', 'TEA', 'DAVY']

    word = 'APPLE'

    print(step_words(word, dictionary))

    print(step_words('DAY', dictionary))