Слово Морф (изменение одной буквы за раз)

Ниже приведена моя реализация решения Word Morph в Python.

Задача состоит в преобразовании одного слова в другое слово путем изменения одной буквы за раз. Каждое слово в цепочке должно быть английским словом (частью словаря). Нужно вывести все такие цепи минимально возможной длины. Примеры: 'tree' до 'fled' цепочка ---- +: = 2 =: + ----, ['tree', 'free', 'flee', 'fled'] до 'man' - 'spa' и ['man', 'may', 'say', 'spy', 'spa']

Комментарии к алгоритму (я сравниваю только листья деревьев, потому что он более эффективен), и общие комментарии были бы очень оценены.

Тесты не были выполнены должным образом, но они не являются моей главной задачей для этого кода.

['man', 'men', 'sen', 'sea', 'spa']
11 голосов | спросил Yulia V 5 J000000Sunday15 2015, 23:15:06

2 ответа


6

Несколько комментариев стиля сначала, а затем на алгоритм:


  • originalLetter, и аналогично названные элементы должны иметь название original_letter, а не как вы их назвали.
  • Функции вроде mergeSortedList ' должен быть строчным, со словами, разделенными символами подчеркивания, по мере необходимости для улучшения удобочитаемости , как это продиктовано PEP8, официальным руководством по стилю Python.
  • i1 следует назвать чем-то более описательным, например item_1
  • i1 = 0; i2 = 0: использование точек с запятой не является питоновым, и его следует избегать любой ценой.
  • if (2*i+1) ' у вас должно быть одно место в этом выражении : (2*i + 1)
  • elif (i1 < len(list1)): Почему вы завершаете все это в скобке, но не if (2*i+1) < len(allLists):, либо все в порядке, просто придерживайтесь полного стандарта.
  • i1 = i1+1: вы можете использовать модификатор += вместо ссылки на переменную: item_1 += 1
  • i2 = i2+1: то же, что и выше: item_2 += 1
  • if errors != '':: вы можете использовать отрицательное выражение с помощью not: if not errors:
  • if ancestor == None:: то же, что указано выше: if not ancestor:
  • if (other == None):, как указано выше: if not other:
  • if len(overlaps)>0:: должен иметь больше пробелов: if len(overlaps) > 0:, но как @JoeWallis указал в комментариях: PEP8 явно говорит, что этот if len(overlaps) > 0: должен быть if overlaps:
    . ' Для последовательностей (строк, списков, кортежей) используйте тот факт, что пустые последовательности являются ложными '

То, что вы пытаетесь решить, называется .

В теории информации и информатике расстояние Левенштейна является строковой метрикой для измерения разницы между двумя последовательностями. Неофициально расстояние Левенштейна между двумя словами - это минимальное количество односимвольных изменений (например, вставки, удаления или замены), необходимые для изменения одного слова на другое.

[ Источник ]

И, как кажется, у Python есть пакет дистанций Левенштейна .

Возможно, вам стоит посмотреть, чтобы улучшить алгоритм.

Или даже примеры Википедии , которые имеют различные примеры, а также пример Python.

ответил Quill 6 J000000Monday15 2015, 01:42:42
10
if ancestor == None:

Часть == None не нужна и добавляет шум вашему коду. Поскольку None является значением false, просто проверка на противоположность от него приведет к True, если он равен None.

Вот что я имею в виду:

if not ancestor:

i2 = i2+1

Заявления, подобные этому, могут быть сокращены до:

i2 += 1

В findChain, когда вы добавляете ошибки в errors, разделите ошибки на новую строку, поэтому, если сообщение об ошибке будет просмотрено позже, различные ошибки будут более легко видны.


if errors != '':
    raise ValueError(errors)

Это можно упростить до

if errors:
    raise ValueError(errors)

Это просто имеет смысл, поскольку вы его читаете ( "Если [есть] ошибки" ).


Не делайте этого:

result.append(list1[i1]); i1 = i1+1

Точки с запятой не совсем питоничны.


Когда вы будете грубыми словами в findNextWords, вы, вероятно, можете ускорить свой алгоритм, следуя некоторым правилам английского языка.

Одним из самых больших и известных английских правил является то, что каждое слово должно иметь гласный.

Затем в findNextWords вы можете установить простой условный код, который проверяет, имеет ли слово хотя бы один гласный. Если это так, то это действительное слово.

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


Я могу добавить больше, поскольку я пытаюсь больше взглянуть на алгоритм.

ответил SirPython 5 J000000Sunday15 2015, 23:28:37

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132