1

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 2

2

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.

1

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)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.