Given a 2d matrix with chars find the target string

Question

I am looking for a simpler implementation of the following question.

Could it get better?

I am expecting the new solution via DFS again. Thanks.

OA: Given a 2d matrix with chars and a target string.

Check if the matrix contains this target string

by only going right or down each time from the beginning point.

public class CharsIncludesString {

        static char[][] matrix = { {'a', 'b', 'c', 'd'},
                                   {'f', 'o', 'u', 'r'} ,
                                   {'r', 'r', 'p', 'c'} ,
                                   {'e', 'f', 'c', 'b'} ,
                                   {'e', 'f', 'c', 'b'}  };


    static int ROW = matrix.length;
    static int COLUMN = matrix[0].length;

    public static void main(String[] args) {

        CharsIncludesString charsIncludesString = new CharsIncludesString();

        String str = "orscb";

        System.out.println( charsIncludesString.checkStr(matrix, str) );

    }

    private boolean checkStr(char[][] matrix, String str) {

        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[i].length;j++){
                if(matrix[i][j] == str.toCharArray()[0]){
                    return dfs(matrix, i, j, str.substring(1));
                }
            }
        }
        return false;
    }

    static class Cell
    {
        public int row;
        public int column;

        public Cell(int row, int column)
        {
            this.row = row;
            this.column = column;
        }
    }

    private boolean dfs(char[][] matrix, int row, int column, String str) {

        if(str.length() == 1)
            return true;

        char[] charArray = str.toCharArray();
        Boolean[][] visited = new Boolean[ROW][COLUMN];

        // Initialize a stack of pairs and
        // push the starting cell into it
        Stack<Cell> stack = new Stack<>();
        stack.push(new Cell(row, column));

        while (!stack.empty())
        {
            Cell curr = stack.pop();

            row = curr.row;
            column = curr.column;

            System.out.print(matrix[row][column] + " ");

            // Push all the adjacent cells
            char c = charArray[0];
            if(matrix[row+1][column] == c)
                dfs(matrix, row +1, column, str.substring(1));
            else if( matrix[row][column+1] == c){
                dfs(matrix, row, column+1 , str.substring(1));
            }else {
                return false;
            }
        }
        return true;
    }

}

Answer 1

The code in your question has some good ideas towards a solution but does not solve the problem and mixes some concepts.

Concept issues

Not sure what the purpose of the stack is there. Usually stacks could be used to mimic call stack and avoid recursion, however the code in the question uses both.

Focusing only on either "DSF with stack" or "DSF with recursion" would help you to the next step.

Bugs

The nested for loop returns on the first iteration, however, it only needs to return on the first true return value of the dsf() call.

Improvements

In case of a recursive solution there's no need for class Cell.

The string passed on every dsf() call is copied each time it is not pooled by Java. This leads to a space complexity of O(n^2) where n is the length of the string. A better solution is to pass on an index.

With the use of static methods class CharsIncludesString doesn't need to be instantiated.

Example code with the fixes from above:

public class CharsIncludesString {

        static char[][] matrix = { {'a', 'b', 'c', 'd'},
                                   {'f', 'o', 'u', 'r'} ,
                                   {'r', 'r', 'p', 'c'} ,
                                   {'e', 'f', 'c', 'b'} ,
                                   {'e', 'f', 'c', 'b'}  };

    public static void main(String[] args) {
        String str = "orpcb";

        System.out.println(checkStr(matrix, str));

    }

    public static boolean checkStr(char[][] matrix, String str) {
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[i].length; j++){
                if (dfs(matrix, i, j, str, 0)) {
                    return true;
                }
            }
        }

        return false;
    }

    public static boolean dfs(char[][] matrix, int row, int column, String str, int strIndex) {
        // no more chars left in str
        if (strIndex >= str.length()) {
            return true;
        }

        // outside of the matrix
        // or the char at [row][column] mismatches with the next char in str
        if (row >= matrix.length || column >= matrix[0].length
            || str.charAt(strIndex) != matrix[row][column]) {
            return false;
        }

        // go right or down
        if (dfs(matrix, row + 1, column, str, strIndex + 1)
            || dfs(matrix, row, column + 1, str, strIndex + 1)) {
            return true;
        }

        return false;
    }

}

Answer 2

What I couldn't deduce from the problem description was the definition of "going right" in the last column (usually it means "go the first cell of the next row") but here it'd might just as well be "not allowed". Same question for "going down" by symmetry.

I next tried to deduce the definition from the code, but noticed that indices [column+1] and [row+1] are not guarded. Unless your code is written in some highly niche language that does auto-wraps, I'd expect it to crash if the substring is not present.

Variable visited is not used, and neither is variable stack. The latter seems to be, but all it experiences during its life is one push followed by one pop. The while always performs exactly 1 loop, so it has no purpose.

The following part is just wrong:

if(matrix[row+1][column] == c)
   ...
else if( matrix[row][column+1] == c)
   ...

If the next row matches but turns out to fail, the next column might match but it's never investigated due to the else.

However, the code can be rescued. If you strip out the useless variables and loop, fix the else-mistake, and handle the "last column/row"-cases, you'll end up with something that is both simpler and actually works.

PS: It all seems strange though. Your code contains the right ingredients (apart from some silly mistakes), but it also contains layers upon it that don't actually do anything. I can only imagine those layers to have been added afterwards. I rescued one down-vote of your question by up-voting it, since I don't expect smoke-screens to be intentional. However, if you don't respond to my answer, I'll assume it was after all and act accordingly.