java - 在给定的字符串数组中搜索单词

Question

You are given a 2D array as a string and a word via keyboard. The word can be in any way (all 8 neighbors to be considered) but you can’t use same character twice while matching. Return word's first and last character's index as (x,y). If match is not found return -1.

这就是问题所在。我在搜索时遇到麻烦。我试过了:

int x=0,y=0;
            for(int f=0; f<WordinArray.length; f++){
                for(int i=0; i<matrix.length; i++){
                    for(int j=0; j<matrix[0].length; j++){
                        if(matrix[i][j].equals(WordinArray[f])){
                            x=i; y=j;
                            System.out.print("("+x+","+y+")");

                        }
                    }
                }
            }

但是，该代码没有按预期工作。我还能怎样编写这个搜索代码？

Answer 1

引用Sixie's code

假设这是您程序的有效输入/输出？

Size:
4x4
Matrix:
a b c d
e f g h
i j k l
m n o p
Word: afkp
(0,0)(3,3)

我编辑了您的代码，以便它可以用于此表单上的输入(目前区分大小写，但可以通过设置 .toLowerCase() 轻松更改

Scanner k = new Scanner(System.in);
System.out.println("Size: ");
String s = k.nextLine();
s.toUpperCase();

int Xindex = s.indexOf('x');
int x = Integer.parseInt(s.substring(0, Xindex));
int y = Integer.parseInt(s.substring(Xindex + 1));

System.out.println("Matrix:");
char[][] matrix = new char[x][y];

for (int i = 0; i < x; i++) {
    for (int p = 0; p < y; p++) {
        matrix[i][p] = k.next().charAt(0);
    }
}

System.out.print("Word: ");
String word = k.next();

int xStart = -1, yStart = -1;
int xEnd = -1, yEnd = -1;

// looping through the matrix
for (int i = 0; i < x; i++) {
    for (int j = 0; j < y; j++) {
        // when a match is found at the first character of the word
        if (matrix[i][j] == word.charAt(0)) {
            int tempxStart = i;
            int tempyStart = j;
            // calculating all the 8 normals in the x and y direction
            // (the 8 different directions from each cell)
            for (int normalX = -1; normalX <= 1; normalX++) {
                for (int normalY = -1; normalY <= 1; normalY++) {
                    // go in the given direction for the whole length of
                    // the word
                    for (int wordPosition = 0; wordPosition < word
                            .length(); wordPosition++) {
                        // calculate the new (x,y)-position in the
                        // matrix
                        int xPosition = i + normalX * wordPosition;
                        int yPosition = j + normalY * wordPosition;
                        // if the (x,y)-pos is inside the matrix and the
                        // (x,y)-vector normal is not (0,0) since we
                        // dont want to check the same cell over again
                        if (xPosition >= 0 && xPosition < x
                                && yPosition >= 0 && yPosition < y
                                && (normalX != 0 || normalY != 0)) {
                            // if the character in the word is not equal
                            // to the (x,y)-cell break out of the loop
                            if (matrix[xPosition][yPosition] != word
                                    .charAt(wordPosition))
                                break;
                            // if the last character in the word is
                            // equivalent to the (x,y)-cell we have
                            // found a full word-match.
                            else if (matrix[xPosition][yPosition] == word
                                    .charAt(wordPosition)
                                    && wordPosition == word.length() - 1) {
                                xStart = tempxStart;
                                yStart = tempyStart;
                                xEnd = xPosition;
                                yEnd = yPosition;
                            }
                        } else
                            break;
                    }
                }
            }
        }
    }
}
System.out.println("(" + xStart + "," + yStart + ")(" + xEnd + ","
        + yEnd + ")");
k.close();