Нахождение слова в двумерном массиве символов

Question

Какой подход может быть простым способом найти заданные слова в такой головоломке? Я использую Java. Спасибо за помощь.

Answer 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 && 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);
        }
    }
}

Answer 2

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

foreach box
    for all directions
        grab the string of characters in that direction
        lookup a dictionary

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

Answer 3

Самый простой подход (концептуально) - просто перечислить все возможные слова в вашем массиве и проверить все в словаре. Словарь, в котором содержится карта, массив строк ... или настоящий словарь, загруженный из Интернета.

В качестве примера приведен код для поиска всех возможных слов по горизонтали ... Добавление другого направления - просто дополнительная работа:

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 result;
  }

}

Это не самое лучшее и эффективное решение. Но это концептуально просто.

РЕДАКТИРОВАТЬ:

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

Диагонали: Я уверен, что вы можете сделать это, если вы поняли код, который я уже ввел. Я не буду делать вашу домашнюю работу или проводить тестирование вместо вас. Попробуй понять, как бы ты это сделал с бумагой и ручкой. Как бы вы это сделали, если бы вам пришлось делать это вручную. Тогда от этого напиши свое решение;)

Answer 4

Я бы поместил список слов в Trie, а затем выполнил бы поиск по всем квадратам во всех направлениях.