Find complete word inside a two-dimensional array

Viewed 100

I have a difficult task. I need to write words to "stringBuilder" cells when they match in a two-dimensional array. This means that I have to find the complete word avoiding duplicate cells. For a better understanding, I will attach a photo of the correct traversal in yellow cells, where red cells are the wrong path.enter image description here

The conclusion should be as follows: [0,2]->[1,2]->[2,2]->[2,3]->[2,4]->[3,4]->[4,4]->[5,4]->[5,3]->[5,2]->[5,1]->[4,1]->[4,0]->[5,0] Now my conclusion is: [5, 0]->[4, 0]->[4, 1]->[4, 2]->[3, 2]->[3, 1]->[2, 1]->[2, 2]->[1, 2]

I can't understand where the failure is and how to fix it, please help.

My code:

public class GFS {
    private static int R;
    private static int C;
    private static int[] x = {-1, 0, 1, 0};
    private static int[] y = {0, 1, 0, -1};
    private static StringBuilder stringBuilder = new StringBuilder();
    private static int indexForWord = 1;

    public static void main(String[] args) {
        R = 7;
        C = 7;
        /*String word = "BOBA";
        String cross = "QWBOABOBGSBSERTY";*/
        /*String word = "KING";
        String cross = "QLGNAEKIRLRNGEAE";*/
        /*String word = "APPLE";
        String cross = "UKJVXNAPBXELPLHVNLDKBVVNM";*/
        String word = "DISABILITATING";
        String cross = "FBDHBAAGNITISTDASABIDDBITILBNILALASGTATIGIYGNTGND";
        char[][] grid = createMatrix(cross);

        search2D(grid, word, 2, 0);
        System.out.println(stringBuilder.toString());
    }

    static char[][] createMatrix(String input) {
        char[][] newArr = new char[R][C];
        int index = 0;
        for (int i = 0; i < newArr.length; i++) {
            for (int j = 0; j < newArr.length; j++) {
                newArr[i][j] = input.charAt(index++);
            }
        }
        return newArr;
    }

    static void print(char[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid.length; j++) {
                System.out.print(grid[i][j] + "  ");
            }
            System.out.println();
        }
    }

    static boolean search2D(char[][] grid, String word, int positionX, int positionY) {
        char oldChar = grid[positionY][positionX];

        if (indexForWord >= word.length()) {
            return true;
        }
        int top = positionY - 1 < 0 ? positionY : positionY - 1;
        int bottom = positionY + 1 >= grid.length ? positionY : positionY + 1;
        int right = positionX + 1 >= grid.length ? positionX : positionX + 1;
        int left = positionX - 1 < 0 ? positionX : positionX - 1;

        if (grid[top][positionX] == word.charAt(indexForWord)) {
            indexForWord++;
            grid[positionY][positionX] = ' ';
            boolean check = search2D(grid, word, positionX, top);
            if (check) {
                stringBuilder.append("[").append(top).append(", ").append(positionX).append("]");
                return true;
            } else {
                for (int j = indexForWord; j >= 0; j--) {
                    if (word.charAt(j) == oldChar) {
                        indexForWord = j + 1;
                        grid[positionY][positionX] = oldChar;
                        break;
                    }
                }
            }
        }
        if (grid[bottom][positionX] == word.charAt(indexForWord)) {
            indexForWord++;
            grid[positionY][positionX] = ' ';
            boolean check = search2D(grid, word, positionX, bottom);
            if (check) {
                stringBuilder.append("[").append(bottom).append(", ").append(positionX).append("]");
                return true;
            } else {
                for (int j = indexForWord; j >= 0; j--) {
                    if (word.charAt(j) == oldChar) {
                        indexForWord = j + 1;
                        grid[positionY][positionX] = oldChar;
                        break;
                    }
                }
            }
        }
        if (grid[positionY][left] == word.charAt(indexForWord)) {
            indexForWord++;
            grid[positionY][positionX] = ' ';
            boolean check = search2D(grid, word, left, positionY);
            if (check) {
                stringBuilder.append("[").append(positionY).append(", ").append(left).append("]");
                return true;
            } else {
                for (int j = indexForWord; j >= 0; j--) {
                    if (word.charAt(j) == oldChar) {
                        indexForWord = j + 1;
                        grid[positionY][positionX] = oldChar;
                        break;
                    }
                }
            }
        }
        if (grid[positionY][right] == word.charAt(indexForWord)) {
            indexForWord++;
            grid[positionY][positionX] = ' ';
            boolean check = search2D(grid, word, right, positionY);
            if (check) {
                stringBuilder.append("[").append(positionY).append(", ").append(right).append("]");
                return true;
            } else {
                for (int j = indexForWord; j >= 0; j--) {
                    if (word.charAt(j) == oldChar) {
                        indexForWord = j + 1;
                        grid[positionY][positionX] = oldChar;
                        break;
                    }
                }
            }
        }
        return false;
    }
}
2 Answers

This is happening because of the indexForWord not being set correct when backtracking from a wrong path and there are duplicate characters(in your case, it's the T)

else {
    for (int j = indexForWord; j >= 0; j--) {
        if (word.charAt(j) == oldChar) {
           indexForWord = j + 1;
           grid[positionY][positionX] = oldChar;
           break;
        }
}

Instead, it is sufficient to just step back once everytime the check is false (in all 4 cases):

else {
       grid[positionY][positionX] = oldChar;
       indexForWord--;
     }

Also the result will be in reverse ([5, 0] -> [4, 0] -> [4, 1] -> [5, 1] etc..), so you will have to reverse it or figure out another approach.

Additionally to what Bahij said :

    private static int indexForWord = 1;

Should be initialized with 0 instead of 1.

Combined with Bahij's solution this yields

[5, 0][4, 0][4, 1][5, 1][5, 2][5, 3][5, 4][4, 4][3, 4][2, 4][2, 3][2, 2][1, 2][0, 2]

(Unfortunately I can't comment on his/her answer because I do not have enough reputation lol)

Related