Задача на составление прямоугольника из слов одинаковой длины

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

Большинство задач, использующих словарь, требуют некоторой предварительной обработки. Как можно провести предварительную обработку?

Если мы собираемся создать квадрат из слов, то длина всех строк и высота всех столбцов должны быть одинаковыми. Давайте сгруппируем слова словаря по длине. Назовем эту группу D, где D[i] — список слов длиной i.

Обратите внимание, что мы ищем самый большой прямоугольник. Какой самый большой квадрат можно сформировать? Это (length(longestWord))^2.

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

Теперь самая сложная часть — makeRectangle(int l, int h). Этот метод пытается создать прямоугольник из слов размером lxh.

Можно, например, пройтись по всем упорядоченным наборам h-слов и затем проверить, содержат ли колонки допустимые слова. Такой метод будет работать, но очень неэффективно.

Предположим, что мы пытаемся создать прямоугольник размером 6×5, и первыми парами строк будут:

  • there
  • queen
  • pizza
  • …..

В этой точке мы уже знаем, что первый столбец начинается с tqp. Мы знаем (или должны знать), что ни одно из слов в словаре не начинается с tqp. Зачем мы продолжили создавать прямоугольник, если знали, что у нас не получится создать допустимый прямоугольник?

Значит, нужна оптимизация. Можно создать выборку, позволяющую упростить поиск, если будем анализировать подстроки как префиксы слов в словаре. При построчном формировании прямоугольника можно ввести проверку, являются ли столбцы допустимыми префиксами. Если нет, мы сразу прекращаем работу с этим прямоугольником.

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

Прежде всего, нам необходима предварительная обработка, позволяющая сгруппировать слова по длине. Мы создаем массив выборок (по одной на каждую длину слова), но пока не будем их использовать.

Метод maxRectangle — главная часть нашего кода. Он начинает работу с самого большого возможного прямоугольника (maxWordLength2) и пытается построить прямоугольник этого размера. Если это невозможно, он пытается создать прямоугольник меньшего размера. Первый прямоугольник, который удастся построить, будет самым большим.

maxRectangle вызывает метод makeRectangle и пытается построить прямоугольник указанных размеров.

Метод makePartialRectangle — наш основной метод, производящий всю работу. Ему передаются окончательные значения длины и высоты, а также частично сформированный прямоугольник. Если нам известно окончательное значение высоты прямоугольника, то мы должны проверить, что колонки содержат допустимые слова, и выйти.

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

Если все нормально и все колонки содержат правильные префиксы, мы перебираем все слова нужной длины, добавляем каждое из них к прямоугольнику и пытаемся построить новый прямоугольник (текущий прямоугольник с новым добавленным словом).

Класс Rectangle представляет собой частотно или полностью сформированный прямоугольник из слов. Метод isPartialOk вызывается для проверки допустимости прямоугольника. Метод isComplete выполняет аналогичную функцию, но дополнительно проверяет, чтобы колонки содержали полное слово.

Класс WordGroup — контейнер, содержащий слова определенной длины. Для упрощения поиска мы будем хранить слова в хэш-таблице так же, как в ArrayList.

Списки в WordGroup создаются с помощью статического метода createWordGroups.

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

Разбор задачи по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию»