Java Word Search Solver Разработка подхода

Question

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

Мой вопрос заключается в том, что при определении местоположения для начальных и конечных символов каждой строки было бы лучше просто провести ее через головоломку с вложенными циклами для каждого направления или этот процесс можно было бы упростить с помощью какой-либо прямойалгоритм обнаружения линии?

Слова могут быть горизонтальными, вертикальными или диагональными и наоборот каждого.

На самом деле я хочу построить начальную и конечную точки массива символов (Слово) внутри массива 2d символов (Головоломка)

Пример головоломки
ХГАМОНИХРА
AOMOKAWONS
NFROLBOBDN
ARFSIHCAGE
LNIEEWONOK
GOLFUNDTHC
KOCATAOHBI
AMRERCGANH
SLGFAMALLC
10 * CO * ALLHATORX 10 10 * 1019 HWH
JABBERWOCKY
CAT
DOG
ALLIGATOR
КУРИЦА
FROG
BANTHA
MOOSE
LLAMA

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

                boolean over = false;
                boolean foundit = false;
                String word = new String(letters);

                for (int i = 0; (i < puzzle.length) && (!over); i++) {
                    for (int j = 0; (j < puzzle[i].length) && (!over); j++) {

                        // Use (i,j) as the starting point.
                        foundit = true;

                        // Look through each letter in word
                        for (int k = 0; (k < letters.length) && (foundit); k++) {
                            if ((j + k >= puzzle[i].length)
                                    || (letters[k] != puzzle[i][j + k])) {
                                // It didn't Match
                                foundit = false;
                            }
                        }
                        // Success if we made it through all the characters
                        if (foundit) {
                            System.out.println(word + " found in row=" + i
                                    + " col=" + j);
                            over = true;
                        }

                    }
                }

                if (!foundit) {
                    System.out.println(word + " not found");
                }

Есть ли какие-нибудь указатели на их нахождение по вертикали, диагонали и наоборот?

Answer 1

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

Вы можете попробовать выбросить всю головоломку в multi_hashmap, где буква - это ключ, а позиция - это значение. Это ускорит поиск (O (1) для поиска, а не O (n), чтобы найти первую букву), но вы, вероятно, не получите большого выигрыша, поскольку вам нужно пройти всю головоломку, чтобы поместить ее в хэш-карту. 1003 *

Грубая сила довольно близка к O (n * m), где n - размер головоломки, а m - количество скрытых слов. (Я предполагаю ограниченную длину слова, скажем, 20.)

Использование hashmap не так уж и много. Это примерно O (n + m), но для небольших головоломок разница не во времени. Хотя это определенно лучше асимптотически. Сделайте оба и сравните их время. Это лучший способ узнать.