recursion - DSA/LC related error

[runic flicker]

Problem : LC 79
error in the picture:

my code:

class Solution {
private:
    bool func(vector<vector<char> > board, string word, int ind,
    int i, int j){
        int n = board.size();
        int m = board[0].size();
        if(ind == word.size()) return true;

        if (i < 0 || i >= n || j < 0 || j >= m ||
         board[i][j] != word[ind] || board[i][j]== ' ')
            return false;

    // we checked it so we replace it with empty element so that we dont check it again
        board[i][j] = ' ';

        bool ans = func(board, word, ind + 1, i - 1, j) || //top
                     func(board, word, ind + 1, i + 1, j) || //bottom
                     func(board, word, ind + 1, i, j - 1) || //left
                     func(board, word, ind + 1, i, j + 1); //right

        return ans;
    }
public:
    bool exist(vector<vector<char> >& board, string word) {
        //your code goes here
        int n = board.size();
        int m = board[0].size();

        for(int i = 0; i<n; i++){
            for(int j=0; j<m; j++){
                if(word[0] == board[i][j]){
                    if(func(board, word, 0, i, j) == true){
                        return true;
                    }
                }
            }
        }
        return false;
    }
};

case on which am getting the error:

board =
[["A","A","A","A","A","A"],["A","A","A","A","A","A"],["A","A","A","A","A","A"],["A","A","A","A","A","A"],["A","A","A","A","A","A"],["A","A","A","A","A","A"]]
word =
"AAAAAAAAAAAAAAB"

[vestal parrot]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

[severe wyvern]

erm

i thing error is pretty clear

and its here, you have ub

int m = board[0].size();

[amber basin]

um no

why is that UB?

[severe wyvern]

because no bounds check on LC lead to test case with board size 0 to have garbage value that probably max uint

[amber basin]

they attached the problem where the error occurs

[severe wyvern]

and they both limit expired

[amber basin]

I suspect the horrific copying of a 2d vector is to blame

m == board.length
n = board[i].length
1 <= m, n <= 6

these are the constraints

there will always be a row 0

although they did mix up m and n in their solutions compared to the example

[severe wyvern]

ok.

check that your recursion have exit tho

run code on your device with debugger

idk maybe they have very very big stack size

i not use lc btw

i not think that just copy vector each time could cause time expired single handed, i saw 10 sec solutions

or something

[runic flicker]

yep that is it, i fixed it, i forgot to backtrack

[amber basin]

there are some issues with your solution

1. vector<vector<char> > board, string word, these are copies. Copying these may be expensive and slow. You don't need to copy string because its never modified. You don't need to copy board if you fix the ' ' you inserted on the return
2. your AAAAAAAAAAAAAAB case is still likely going to fail because your algorithm is too inefficient at solving it. There is no B but thats the last character, so its going to search for the 13 As first and then fail at the B. Every time your recurse you do 4x the path checks (on average). So you're doing 6*6 (the size of the grid) checks of 4^13 paths. Thats 2415919104 paths which all fail, not exactly a fast solution

you could do a first check where you test how many of each character there is in the grid and the word to quickly prove a solution isn't findable in such cases

[runic flicker]

had to store the board[i][j] in a temp variable and then go look for the other remaining letters of the word then after that gotta backtrack the original value so that loop runs smoothly

copying took too much memory

[amber basin]

yep

You don't need to copy board if you fix the ' ' you inserted on the return
exactly as I was suggesting

[runic flicker]

thanks guys!

!solved

[vestal parrot]

Thank you and let us know if you have any more questions!

This thread is now set to auto-hide after an hour of inactivity

[amber basin]

but your algorithm still is inefficient at proving this test case fails

[runic flicker]

i see, any suggestions for improving that?

[amber basin]

read my 2 messages

[runic flicker]

1sec

[runic flicker]

I see, so should i go store them in a hash map and check? Or there's a better way than this?
(Am amateur at dsa)

[amber basin]

yeah some sort of hashmap. Although if it passes already its not really a big deal