如何遍历在java中搜索单词的二维字符数组? [英] how to traverse though a 2d char array searching for words in java?

问题描述

我在完成一项学校作业时遇到了问题，非常感谢您提供一些见解.我被要求使用 25x25 2d 字符数组创建单词搜索，并通过开发一种算法以某种方式遍历该数组，该算法将搜索它以找到 21 个预定义的单词.

I am having trouble with a school assignment and would really appreciate some insight. I am asked to create a wordsearch using a 25x25 2d char array and somehow go through that array by developing an algorithm that will search through it to find 21 pre-defined words.

到目前为止，我已经能够创建一个由我需要查找的单词组成的参差不齐的数组，以及在每个位置放置字符的二维数组.

So far I have been able to create a ragged array of the words that I need to find and the 2d array with the chars placed in each position.

in = new ASCIIDataFile("wordsearch.txt");
display = new ASCIIDisplayer();
int numberWords = in.readInt();

wordlist = new char[numberWords][];

for (int i =0; i<wordlist.length; i++){
  wordlist[i] = in.readLine().toUpperCase().toCharArray(); 
}
for(int i = 0;i<wordlist.length; i++){
  display.writeLine(" ");
  for(int j = 0;j<wordlist[i].length; j++){
    display.writeChar(wordlist[i][j]);
  }
}
//done wordlists

int gridLength = in.readInt();
int gridHeight = in.readInt();

grid = new char[gridHeight][gridLength];

for(int i = 0;i<gridLength; i++){
  grid[i] = in.readLine().toCharArray();

}

我在创建算法以搜索二维数组并将其与单词列表中的字符匹配时遇到的问题.我应该做出不同的方法，用于向前、向后和对角线搜索.为了向前搜索，我已经挣扎了好几天.

My problem in creating the algorithm to search though the 2d array and match it with a character in the wordlist. I am supposed to make different methods, for searching forwards, backwards and diagonal. I have been struggling for days just to do the forward search.

我真的不知道如何解决这个问题，到目前为止我只有

I really how no idea about how to go about this problem, so far all I have is

for(int k = 0; k<wordlist.length; k++){
  int p = 0;
  for(int row = 0;row<gridLength; row++){
    for(int col = 0;col<gridHeight; col++){

      while(p<wordlist[k].length){
        if(grid[row][col] == wordlist[k][p]){

          //do something

        }
      }
    }
  }
}    

}

任何帮助或指示将不胜感激！

Any help or pointers would be greatly appreciated!

推荐答案

诀窍是，您不需要分别考虑所有 8 个可能的方向.你可以用一个向量来表示每个.例如，向前"方向将是 (0, 1)(第一个行号，然后是列)——一个指向右侧的向量.对角线左上角方向为 (-1, -1).反正你懂这个意思.

The trick is, you don't need to consider all 8 possible directions separately. You can represent each with a vector. E.g., 'forward' direction would be (0, 1) (first row number, then column) - a vector pointing to the right. Diagonal top-left direction would be (-1, -1). Well, you get the idea.

然后，创建一个函数

boolean findWord(int row, int col, int d_row, int d_col, char[] word);

它可以获取当前矩阵位置((row, col)，单词应该从哪里开始)、搜索方向((d_row, d_col))和一个单词寻找.它返回给定的单词是否在这里.
然后你可以为不同的方向调用它，例如

It can take current matrix position ((row, col), where word is supposed to start), search direction ((d_row, d_col)) and a word to look for. It returns whether the given word is here.
Then you can invoke it for different directions, e.g.

findWord(row, col, -1, 0, word);
findWord(row, col, -1, 1, word);
findWord(row, col, 0, 1, word);
...

(我按顺时针顺序列出它们)

(I'm listing them in clock-wise order)

实现findWord 只是通过d_row 和d_col 增加当前位置，直到我们发现字符或词尾不匹配.基本套路是这样的

Implementing findWord is just incrementing current position by d_row and d_col, until we find mismatch in characters or word ends. The basic routine is like this

while (row < total_rows && row >= 0 && col < total_columns && col >= 0) {
    // check character here
    ...
    row += d_row;
    col += d_col;
}

我敢打赌，您将在 40 行中包含所有处理代码(输入读取除外).

I bet you'll have all processing code (except input-reading) in 40 lines.

这篇关于如何遍历在java中搜索单词的二维字符数组?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！