#java #algorithm #string
#java #алгоритм #строка
Вопрос:
Какой подход может быть простым способом найти заданные слова в подобной головоломке? Я использую Java. Спасибо за помощь.
Комментарии:
1. Вы уже что-то пробовали? Это домашнее задание? Дополнительная информация, пожалуйста!
2. Это не домашнее задание, я просто практикуюсь. Данные не поступают. Я пробовал что-то со многими циклами for, которые сравнивают символы, но я думаю, что должен быть более простой способ. Я ищу слова по вертикали и горизонтали, а также по диагонали.
Ответ №1:
Интересный вопрос. Я бы решил это, сначала создав список «возможных держателей слов» (последовательности символов, которые, возможно, могут содержать одно из заданных слов), пройдя головоломку по горизонтали, вертикали и диагонали (в обоих направлениях). Затем я хотел бы посмотреть, присутствуют ли указанные слова (или их обратные значения) (используя метод contains() в Java) в каждом из полученных «возможных держателей слов». Вот код, который я написал на Java. Я не тестировал это должным образом, но я предполагаю, что это работает!
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
public class WordPuzzle {
public Set<String> findWords(char[][] puzzle, Set<String> words) {
Set<String> foundWords = new HashSet<String>();
int minimumWordLength = findMinimumWordLength(words);
Set<String> possibleWords = findPossibleWords(puzzle, minimumWordLength);
for(String word : words) {
for(String possibleWord : possibleWords) {
if(possibleWord.contains(word) || possibleWord.contains(new StringBuffer(word).reverse())) {
foundWords.add(word);
break;
}
}
}
return foundWords;
}
private int findMinimumWordLength(Set<String> words) {
int minimumLength = Integer.MAX_VALUE;
for(String word : words) {
if(word.length() < minimumLength)
minimumLength = word.length();
}
return minimumLength;
}
private Set<String> findPossibleWords(char[][] puzzle, int minimumWordLength) {
Set<String> possibleWords = new LinkedHashSet<String>();
int dimension = puzzle.length; //Assuming puzzle is square
if(dimension >= minimumWordLength) {
/* Every row in the puzzle is added as a possible word holder */
for(int i = 0; i < dimension; i ) {
if(puzzle[i].length >= minimumWordLength) {
possibleWords.add(new String(puzzle[i]));
}
}
/* Every column in the puzzle is added as a possible word holder */
for(int i = 0; i < dimension; i ) {
StringBuffer temp = new StringBuffer();
for(int j = 0; j < dimension; j ) {
temp = temp.append(puzzle[j][i]);
}
possibleWords.add(new String(temp));
}
/* Adding principle diagonal word holders */
StringBuffer temp1 = new StringBuffer();
StringBuffer temp2 = new StringBuffer();
for(int i = 0; i < dimension; i ) {
temp1 = temp1.append(puzzle[i][i]);
temp2 = temp2.append(puzzle[i][dimension - i - 1]);
}
possibleWords.add(new String(temp1));
possibleWords.add(new String(temp2));
/* Adding non-principle diagonal word holders */
for(int i = 1; i < dimension - minimumWordLength; i ) {
temp1 = new StringBuffer();
temp2 = new StringBuffer();
StringBuffer temp3 = new StringBuffer();
StringBuffer temp4 = new StringBuffer();
for(int j = i, k = 0; j < dimension amp;amp; k < dimension; j , k ) {
temp1 = temp1.append(puzzle[j][k]);
temp2 = temp2.append(puzzle[k][j]);
temp3 = temp3.append(puzzle[dimension - j - 1][k]);
temp4 = temp4.append(puzzle[dimension - k - 1][j]);
}
possibleWords.add(new String(temp1));
possibleWords.add(new String(temp2));
possibleWords.add(new String(temp3));
possibleWords.add(new String(temp4));
}
}
return possibleWords;
}
public static void main(String args[]) {
WordPuzzle program = new WordPuzzle();
char[][] puzzle = {
{'F','Y','Y','H','N','R','D'},
{'R','L','J','C','I','N','U'},
{'A','A','W','A','A','H','R'},
{'N','T','K','L','P','N','E'},
{'C','I','L','F','S','A','P'},
{'E','O','G','O','T','P','N'},
{'H','P','O','L','A','N','D'}
};
Set<String> words = new HashSet<String>();
words.add("FRANCE");
words.add("POLAND");
words.add("INDIA");
words.add("JAPAN");
words.add("USA");
words.add("HOLLAND");
Set<String> wordsFound = program.findWords(puzzle, words);
for(String word : wordsFound) {
System.out.println(word);
}
}
}
Комментарии:
1. Я думаю, вы рассматриваете только главную диагональ, как насчет остальных?
2. Я рассмотрел все диагонали. Однако, возможно, у меня слишком сложный обход диагоналей. Вскоре я обновлю решение более элегантным. Тем не менее, данное решение, казалось, работало для всех диагоналей. Или я недостаточно протестировал?
3. Ага. Казалось, это работает для всех случаев. Хотя я не тестировал его тщательно.
4. Я только что исправил ошибку в предыдущем коде. Обновленный код, похоже, работает нормально.
5. Спасибо Витуну. Есть ли какой-либо способ связаться с вами напрямую?
Ответ №2:
В общем, я предлагаю использовать самый наивный подход, если только ваши головоломки не будут большими. Я бы не стал оптимизировать ничего, что занимает менее 0,1 с, но это только у меня.
foreach box
for all directions
grab the string of characters in that direction
lookup a dictionary
Я думаю, что ум может заключаться в том, как вы разрабатываете свой словарь. В этом случае я бы создал многоуровневую хэш-таблицу, где символы выбирают, какую хэш-таблицу просматривать на следующем уровне.
Комментарии:
1. Для меня цикл for — это наиболее интуитивно понятный способ перебора по нему. Меньше размышлений и отладки в этом коде.
2. Хэш уровня mutli — это оптимизация для ускорения поиска по словарю, если это то, что вы имеете в виду. Возможно, вам придется это сделать, если словарь большой.
Ответ №3:
Я бы поместил список слов в дерево, затем выполнил поиск по всем квадратам во всех направлениях.
Ответ №4:
Самый простой подход (концептуально) — просто перечислить все возможные слова в вашем массиве и затем проверить все в словаре. Словарь, содержащий карту, массив строк… или настоящий словарь, загруженный из Интернета.
В качестве примера здесь приведен код для поиска всех возможных слов по горизонтали… Добавление другого направления — это просто дополнительная работа :
import java.util.HashSet;
import java.util.Set;
public class WordFinder {
public static void main(String[] args) {
String[][] words = { { "F", "Y", "Y", "H", "N", "R", "D" },
{ "R", "L", "J", "C", "I", "N", "U" },
...};
Set<String> dictionnary = new HashSet<String>();
dictionnary.add(...);
Set<String> wordsFound = findWords(words, dictionnary);
...
}
/**
* Find all words in the specified array present in the dictionnary.
*
*/
private static Set<String> findWords(String[][] words, Set<String> dictionnary) {
Set<String> wordsFound = new HashSet<String>();
// Find all possible words horizontally :
int nbrRows = words.length;
int nbrCol = words[0].length; // We suppose we have at least one row and all row have same lengh
// Iterate through all rows
for (int currentRow = 0; currentRow < nbrRows; currentRow ) {
// Iterate through all possible starting position in the current row.
for (int beginWordIndex = 0; beginWordIndex < nbrCol; beginWordIndex ) {
// Iterate then through all possible ending positions in the current row, so to deal with word of any lengh.
for (int endWordIndex = beginWordIndex; endWordIndex < nbrCol; endWordIndex ) {
// Construct a word from the begin/end indexes :
String currentWord = getWordInRow(words, currentRow, beginWordIndex, endWordIndex);
// Check if the word candidate really exist, if yes, store it in the wordsFound variable.
if (dictionnary.contains(currentWord)) {
wordsFound.add(currentWord);
}
// The reverse
String reverseWord = reverseString(currentWord);
// Check if the reverse word really exist, if yes, store it in the wordsFound variable.
if (dictionnary.contains(reverseWord)) {
wordsFound.add(currentWord);
}
}
}
}
// Don't forget vertically and in diagonals too... Same principe.
return wordsFound;
}
/**
* Return a word "candidate" in the specified row, starting at beginIndex and finishing at endIndex.
*/
private static String getWordInRow(String[][] words, int row, int beginIndex, int endIndex) {
String currentWord = "";
int currentPosition = beginIndex;
while (currentPosition <= endIndex) {
currentWord = words[row][currentPosition];
}
return currentWord;
}
/**
* Return the reverse of a String
*/
private static String reverseString(String string) {
String result = "";
for (int i = string.length()-1; i >=0;i ) {
result = string.charAt(i);
}
return resu<
}
}
Это не лучшее, наиболее эффективное решение. Но это концептуально просто.
Редактировать :
обратный порядок: смотрите отредактированный код. Просто напишите функцию, которая может перевернуть слово. Поскольку у нас уже есть все возможные слова в обычном порядке, достаточно поменять их местами, чтобы слова располагались в обратном порядке.
Диагонали: Я уверен, что вы сможете это сделать, если вы поняли код, который я уже ввел. Я не буду делать вашу домашнюю работу или проводить тестирование вместо вас. Попробуйте представить, как бы вы это сделали с бумагой и ручкой. Как бы вы это сделали, если бы вам пришлось делать это вручную. Затем на основе этого напишите свое решение 😉