Блог

Пошаговое слово формируется путем взятия заданного слова, добавления буквы и анаграмм результата. Например, начиная со слова «APPLE», вы можете добавить «A» и анаграмму, чтобы получить «АПЕЛЛЯЦИЮ».

Учитывая глобальный словарь слов, создайте функцию step(word), которая возвращает список всех уникальных допустимых слов step, появляющихся в словаре.

Словарь: 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']
  

Как мы знаем, анаграммы в отсортированном виде точно такие же.

Логические:

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))

  

Поскольку в анаграммах одни и те же буквы, если вы отсортируете буквы в слове по алфавиту, вы получите одну и ту же строку для слов, которые являются анаграммами друг друга. Например: LEAP -> сортировка по алфавиту -> AEPL PALE -> сортировка по алфавиту -> AEPL

1) Вы должны перебрать все слова в вашем словаре и создать поиск по алфавитно отсортированному строковому ключу в списке слов, которые имеют один и тот же ключ.

Дан список слов

 ["PALE","LEAP"]
  

вы получите поиск анаграммы следующим образом

 {
"AEPL"=>["PALE","LEAP"],
...
} 
  

2) Затем возьмите входное слово и попробуйте разные комбинации алфавитов, чтобы создать новую строку. Отсортируйте эту строку и найдите совпадения в словаре анаграмм. Объедините возвращаемые списки в один список и верните этот список.

Допустим, входное слово — PEA, сгенерируйте все комбинации

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

Сортировка по алфавиту каждого слова-кандидата

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

Затем выполните поиск и объединение возвращенных списков

 ["LEAP","PALE"]
  

Дайте мне знать, если вам нужен код python и здесь, но это должно быть легко закодировать. Ускорение в первую очередь связано с предварительной обработкой словаря поиска анаграмм, благодаря чему окончательный поиск выполняется почти постоянно, но при этом используется дополнительное пространство порядка слов во входном списке.

Пожалуйста, ознакомьтесь с реализацией и пояснениями ниже: Для этой проблемы мы можем разделить ее на две части: сначала попробуйте создать карту слов, используя 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))

  

Вот простой фрагмент кода, который: прочитайте файл и создайте таблицу поиска. Есть некоторый код для обработки особых случаев, найденных в файле.

 ## letters which will be added to the word to lookup for anagrams
alphabet = 'abcdefghijklmnopqrstuvwxyz'


## read the file, lowercase the letters, and split it in case you have some blanks
dictionary = open('words.txt', encoding='ascii').read().lower().split()


## build a lookup dict which holds all words for a given sorted set of letters
lookup = {}
for word in dictionary:
    try:
        if word not in lookup[''.join(sorted(word))]:   ## avoid possible duplicates in the dictionary if word is already in the dictionnary, like anagrams, or Upper/lowercase
            lookup[''.join(sorted(word))].append(word)
    except:
        lookup[''.join(sorted(word))] = [word] ## create new dictionnary entry if key does not exists


## step function to find anagrams with one more letter
def step(word):
    word = word.lower() ## works with lowercase word only
    output = []
    for i in alphabet: ## try to find anagrams with one extra letter added to the word
        try:
            output  = lookup[''.join(sorted(word i))] ## add the word found if an anagram is found in lookup dict
        except:
            pass
    return list(set(output)) ## be sure to return only unique answers in a list


## main
if __name__ == '__main__':
    print (step('aPPle'))
    print (step('OV'))      ## test for the dupes 'Ova' and 'ova' found in the file
    print (step('a'))       ## test for the one letter dupes 'a' and 'A' found in the file
    print (step('A'))       ## test for the one letter dupes 'a' and 'A' found in the file
  

Приведенная ниже программа выполнит поиск нескольких комбинаций входной строки и выведет анаграммы. Это можно доработать, но это основная отправная точка для проверки допустимых значений анаграммы.

 #Program: Anagram Finder

from itertools import permutations

#Store the words text file in to an object for searching

with open('words.txt', 'r') as f:
    dictionary = f.read()
    dictionary = [x.lower() for x in dictionary.split('n')]

#Get permutations of input word
def get_perms(value, length):
    for l in range(length):
        for perm in permutations(value, l):
            yield ''.join(perm)
    else:
        return []

# Search the dictionary for possible Anagrams and list the valid ones
def fncSearchForAnagram():

  y = ["Apple"] # Anagram check Sample input.
  for i in y:
      perms = get_perms(i, len(i))
      for item in perms:
          if item.lower() in dictionary:  # converting search string to lower since the word file has all lower case chars
              # This output will be your Anagram combination word listed in the Words.txt File
              print(item)


fncSearchForAnagram()
  

Чтобы легко проверить, является ли слово анаграммой другого, мы сначала сортируем оба слова. И проверьте, равны ли они после сортировки. Поскольку анаграмма — это просто перестановка символов. Чтобы проверить, можем ли мы добавить в word некоторый символ для создания другого слова, мы просто проверяем, присутствуют ли символы слова в другом слове.

 list_of_words = ['handsome', 'handy', 'notright', 'and']
word_to_check = 'adn'

anagram_can_add_chars= []
anagram_cannot_add_chars= []

# loop through the list of words
for word in list_of_words:

  # we sort the string so that we know that we have all the chars
  if sorted(word_to_check) == sorted(word):
    anagram_cannot_add_chars.append(word)

  # we convert the strings to set
  # this will remove duplicate chars on each
  # but we can always add them 
  if set(sorted(word_to_check)).issubset(set(sorted(word))):
    anagram_can_add_chars.append(word)

print(anagram_can_add_chars)
print('---')
print(anagram_cannot_add_chars)
  

Результат :

 ['handsome', 'handy', 'and']
---
['and']