在二維字符數組上找到一個詞

Question

什麼樣的接近可能是一種簡單的方法來找到這樣的謎題上的給定單詞？我正在使用Java。感謝幫助。

Answer 1

有趣的問題。我首先通過水平，垂直和對角（兩個方向）遍歷拼圖構建一個「可能的單詞持有者」（可能包含某個給定單詞的字符序列）列表來解決這個問題。然後，我會在每個獲得的「可能的單詞持有者」中看到給定的單詞（或其反向）是否存在（在Java中使用contains（）方法）。這是我在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.1s的任何東西，但那只是我。

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

我覺得智能可以在你如何設計你的字典。在這種情況下，我會做一個多級哈希表，其中字符選擇哪個哈希表來查看下一個級別。

Answer 3

我會把單詞列表放到Trie中，然後從所有方向的所有方塊中進行搜索。

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

} 

這是不是最好的，最有效的解決方案。但它在概念上很簡單。

編輯：

逆序：請參閱編輯的代碼。只需編寫一個可以翻轉單詞的函數。因爲我們已經有了正常順序的所有可能的單詞，所以顛倒它們就足以讓單詞以相反的順序排列。

對角線：如果您已經理解了我已經放入的代碼，那麼您確定可以這樣做。我不會做你的功課或做你的測試來代替你。試着弄清楚如何用紙和筆來做到這一點。如果你必須親自去做，你會怎麼做？然後從中，寫下你的解決方案;）