Условие задачи звучит так: дан список из миллиона слов. Разработайте алгоритм, создающий максимально возможный прямоугольник из букв так, чтобы каждая строка и каждый столбец образовывали слово (при чтении слева направо и сверху вниз). Слова могут выбираться в любом порядке, строки должны быть одинаковой длины, а столбцы — одинаковой высоты.
Большинство задач, использующих словарь, требуют некоторой предварительной обработки. Как можно провести предварительную обработку?
Если мы собираемся создать квадрат из слов, то длина всех строк и высота всех столбцов должны быть одинаковыми. Давайте сгруппируем слова словаря по длине. Назовем эту группу D, где D[i] — список слов длиной i.
Обратите внимание, что мы ищем самый большой прямоугольник. Какой самый большой квадрат можно сформировать? Это (length(longestWord))^2.
int maxRectangle = longestWord * longestWord;
for z = maxRectangle to 1 {
for each pair of numbers (i,j) where i*j = z {
/* пытаемся создать прямоугольник, возвращаемся, если успешно */
}
}
Мы проходим по прямоугольникам от самого большого до самого маленького, таким образом, первый найденный прямоугольник будет самым большим.
Теперь самая сложная часть — makeRectangle(int l, int h). Этот метод пытается создать прямоугольник из слов размером lxh.
Можно, например, пройтись по всем упорядоченным наборам h-слов и затем проверить, содержат ли колонки допустимые слова. Такой метод будет работать, но очень неэффективно.
Предположим, что мы пытаемся создать прямоугольник размером 6×5, и первыми парами строк будут:
there
queen
pizza
…..
В этой точке мы уже знаем, что первый столбец начинается с tqp. Мы знаем (или должны знать), что ни одно из слов в словаре не начинается с tqp. Зачем мы продолжили создавать прямоугольник, если знали, что у нас не получится создать допустимый прямоугольник?
Значит, нужна оптимизация. Можно создать выборку, позволяющую упростить поиск, если будем анализировать подстроки как префиксы слов в словаре. При построчном формировании прямоугольника можно ввести проверку, являются ли столбцы допустимыми префиксами. Если нет, мы сразу прекращаем работу с этим прямоугольником.
Приведенный далее код реализует этот алгоритм. Это длинный и сложный алгоритм, поэтому мы будем анализировать его по частям.
Прежде всего, нам необходима предварительная обработка, позволяющая сгруппировать слова по длине. Мы создаем массив выборок (по одной на каждую длину слова), но пока не будем их использовать.
WordGroup[] groupList = WordGroup.createWordGroups(list);
int maxWordLength = groupList.length;
Trie trieList[] = new Trie[maxWordLength];
Метод maxRectangle — главная часть нашего кода. Он начинает работу с самого большого возможного прямоугольника (maxWordLength2) и пытается построить прямоугольник этого размера. Если это невозможно, он пытается создать прямоугольник меньшего размера. Первый прямоугольник, который удастся построить, будет самым большим.
Rectangle maxRectangleO {
int maxSize = maxWordLength * maxWordLength;
for (int z = maxSize; z > 0; z--) { // начинаем с наибольшей области
for (int i = 1; i <= maxWordLength; i ++ ) {
if (z % i == 0) {
int j = z / i;
if (j <= maxWordLength) {
/* Создаем прямоугольник длиной i и высотой j.
* Заметьте, что i * j = z. */
Rectangle rectangle = makeRectangle(i, j);
if (rectangle != null) {
return rectangle;
}
}
}
}
}
return null;
}
maxRectangle вызывает метод makeRectangle и пытается построить прямоугольник указанных размеров.
Rectangle makeRectangle(int length, int height) {
if (groupList[length-l] == null ||
groupList[height-l] == null) {
return null;
}
/* Создает выборку для длины слова, если мы ее еще не создали */
if (trieList[height-1] == null) {
LinkedList words = groupListfheight-1) .getWordsQ;
trieList[height-1] = new Trie(words);
}
return makePartialRectangle(length, height,
new Rectangle(length));
}
Метод makePartialRectangle — наш основной метод, производящий всю работу. Ему передаются окончательные значения длины и высоты, а также частично сформированный прямоугольник. Если нам известно окончательное значение высоты прямоугольника, то мы должны проверить, что колонки содержат допустимые слова, и выйти.
В противоположном случае мы проверяем, сформированы ли столбцы из допустимых префиксов. Если нет, работа останавливается, поскольку нет смысла продолжать строить этот прямоугольник.
Если все нормально и все колонки содержат правильные префиксы, мы перебираем все слова нужной длины, добавляем каждое из них к прямоугольнику и пытаемся построить новый прямоугольник (текущий прямоугольник с новым добавленным словом).
Rectangle makePantialRectangle(int 1, int h, Rectangle rectangle) {
if (rectangle.height == h) { // Проверяем, полный ли прямоугольник
if (rectangle.isComplete(l, h, groupList[h-1])) {
return rectangle;
} else {
return null;
}
}
/* Сравниваем колонки с выборкой, чтобы увидеть */
/* потенциально допустимый прямоугольник */
if (!rectangle.isPartialOK(l, trielist[h-1])) {
return null;
}
/* Проходимся по всем словам нужной длины. Добавляем каждое в
* текущий частичный прямоугольник и пытаемся построить прямоугольник
* рекурсивно. */
for (int i=0; i<groupList[l-l].length(); i++) {
/* Создаем новый прямоугольник, добавляя новое слово в текущий */
Rectangle orgPlus = rectangle.append(groupList[l-l].getWord(i));
/* Пытаемся построить прямоугольник с этим новым, */
/* частичным прямоугольником */
Rectangle rect = makePartialRectangle(l, h, orgPlus);
if (rect != null) {
return rect;
}
}
return null;
}
Класс Rectangle представляет собой частотно или полностью сформированный прямоугольник из слов. Метод isPartialOk вызывается для проверки допустимости прямоугольника. Метод isComplete выполняет аналогичную функцию, но дополнительно проверяет, чтобы колонки содержали полное слово.
public class Rectangle {
public int height, length;
public char [][] matrix;
/* Создаем "пустой" прямоугольник. Длина - фиксированная, но высота
* может изменяться при добавлении слов */
public Rectangle(int 1) {
height = 0;
length = 1;
}
/* Создаем прямоугольный массив слов
* определенной длины и высоты
* (Предполагается, что длина и высота определены
* как аргументы и не противоречат
* размерам массива) */
public Rectangle(int length, int height, char[][] letters) {
this.height = letters.length;
this.length = letters[0].length;
matrix = letters;
}
public char getLetter (int i, int j) { return matrix[i][j]; }
public String getColumn(int i) { ... }
/* Проверяем, все ли колонки допустимы. Все строки будут
* допустимы, так как они были добавлены непосредственно из словаря */
public boolean isComplete(int 1, int h, WordGroup groupList) {
if (height == h) {
/* Проверяем, является ли каждая колонка словарным словом*/
for (int i = 0; i < 1; i++) {
String col = getColumn(i);
if (!groupList.containsWord(col)) {
return false;
}
}
return true;
}
return false;
}
public boolean isPartialOK(int 1, Trie trie) {
if (height == 0) return true;
for (int i = 0; i < 1; i++ ) {
String col = getColumn(i);
if (!trie.contains(col)) {
return false;
}
}
return true;
}
/* Создаем новый Rectangle: берем строки текущего
* прямоугольника и добавляем s. */
public Rectangle append(String s) { ... }
}
Класс WordGroup — контейнер, содержащий слова определенной длины. Для упрощения поиска мы будем хранить слова в хэш-таблице так же, как в ArrayList.
Списки в WordGroup создаются с помощью статического метода createWordGroups.
public class WordGroup {
private Hashtable<String, Boolean> lookup =
new Hashtable<String, Boolean>();
private ArrayList group = new ArrayList();
public boolean containsWord(String s) {
return lookup.containsKey(s));
}
public void addWord (String s) {
group.add(s);
lookup.put(s, true);
}
public int lengthQ { return group.size(); }
public String getWord(int i) { return group.get(i); }
public ArrayList getWords() { return group; }
public static WordGroup[] createWordGroups(String[] list) {
WordGroupf] groupList;
int maxWordLength = 0;
/* Находим длину самого длинного слова */
for (int i = 0; i < list.length; i++) {
if (list[i].length() > maxWordLength) {
maxWordLength = list[i].length();
}
}
/* Группируем слова в словаре в списки одинаковой длины
* length.groupList[i] будет содержать список слов
* длиной (i+1). */
groupList = new WordGroup[maxWordLength];
for (int i = 0; i < list.length; i++) {
/* Мы делаем wordLength - 1 вместо просто wordLength,
* так как мы используем wordLength и нет слов длиной 0 */
int wordLength = list[i].length() - 1;
if (groupList[wordLength] == null) {
groupList[wordLength] = new WordGroupO;
}
groupList[wordLength].addWord(list[i]);
}
return groupList;
}
}
Полный код для этой задачи, включая коды методов Trie и TrieNode, вы можете скачать с сайта автора книги. Не забудьте, что в подобных сложных задачах лучше использовать псевдокод. На написание полного кода вам просто не хватит времени.
Разбор задачи по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию»
