如何遍历二维字符数组在java中搜索单词？

Question

我在完成学校作业时遇到困难，非常希望获得一些见解。我被要求使用 25x25 2d 字符数组创建一个单词搜索，并以某种方式通过开发一种算法来遍历该数组，该算法将搜索该数组以查找 21 个预定义单词。

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

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();

}

我的问题是创建算法来搜索二维数组并将其与单词列表中的字符进行匹配。 我应该采用不同的方法来向前、向后和对角搜索。 我已经努力了几天只是为了进行向前搜索。

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

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

        }
      }
    }
  }
}    

}

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

Answer 1

诀窍是，您不需要单独考虑所有 8 个可能的方向。您可以用向量来表示每个。例如，“向前”方向将是 (0, 1) （第一个行号，然后是列） - 指向右侧的向量。左上角对角线方向为(-1, -1)。好吧，你明白了。

然后，只需创建一个函数

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

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

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

（我按顺时针顺序列出它们）

实现 findWord 只是将当前位置增加 d_row 和 d_col，直到我们发现字符或词尾不匹配。基本例程是这样的，

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

我打赌您将在 40 行内掌握所有处理代码（除了输入读取）。

Answer 2

您首先需要了解如何在较大字符串中搜索短字符串。这里有几个选择：从最简单的算法到更复杂的算法（如 Knuth Morris Pratt 和家人）。您可以在此处获取其描述列表：http://en.wikipedia.org/wiki/String_searching_algorithm。我强烈建议您首先尝试简单搜索。

一旦您可以在另一个字符串中搜索一个字符串，您将需要抽象访问更大字符串的方式并使矩阵数据适应它。

基本上假设这个矩阵：

   1 2 3 4 
   -------
1| a b c d 
2| b c d a
3| c d a b
4| d a b c

和这个字符串 abc

您将首先编写一些代码以便能够在 abcd 或 bcda 或 中找到 abc 一旦你能做到这

一点，你应该构建提取（对于每种可能的查找类型：水平、垂直、对角线、反对角线）字符系列的中间步骤，并对它们应用之前的算法。

例如，如果我们想对角搜索，我们将从矩阵中生成 7 个字符串：

a
bb
ccc
dddd
aaa
bb
c

如果您想水平搜索，您将生成这些字符串：

abcd
bcda
cdab
dabc

并在每个字符串内进行搜索。

一旦它起作用，您应该将搜索与从矩阵中读取正确的字符结合起来。希望如果您遵循这条道路，您将能够弄清楚:)。

祝你好运。

Answer 3

要在任意维度的任何二维矩阵中对角移动，希望以下函数有所帮助。

public static void prinDiagonalsInGrid(char[][] grid, int rows, int cols)
{
    String result = "";
    int min = Math.min(rows, cols);
    int max = Math.max(rows, cols);

    int sameLengthDiagonals = max - min + 1;
    int totalDiagonals = (rows + cols) - 1;

    for (int p = 0; p < totalDiagonals; p++)
    {
        int xIndex;
        int maxCnt;

        if (p < (min - 1)) // First diagonals
        {
            maxCnt = xIndex = p;
        }
        // diagonals of equal length in the middle
        else if (sameLengthDiagonals != 0 &&
                 p >= (min - 1) && p < (sameLengthDiagonals + min - 1))
        {
            if (rows < cols)
                xIndex = rows - 1;
            else
                xIndex = p;
            maxCnt = min - 1;
        }
        else  // Last diagonals
        {
            xIndex = rows - 1;
            maxCnt = totalDiagonals - p - 1;
        }

        for (int cnt = 0; cnt <= maxCnt; cnt++)
        {
            result += grid[xIndex][p - xIndex] + "    ";
            --xIndex;
        }
        result += "\n";
    }
    System.out.println(result);
}