Why my DFS solution is so slow?


  • 1
    M

    Hi, I came up a DFS solution and it was accepted. But I don't know why it is so slow (only beats 2%). I check some other posts and I think my idea is very close to the answer of @dong.wang.1694 posted here which beats over 90%. Below is my code:

    class Solution {
    public:
        bool search(int i, int j, string& word, int current, vector<vector<char>>& board, int& m, int& n, int& len) {
            if (current == len - 1 && word[current] == board[i][j]) {
                return true;
            }
            else {
                char c = board[i][j];
                board[i][j] = '*';
                vector<vector<int>> dirs = {{-1,0},{1,0},{0,-1},{0,1}}; //Up, down,left,right
                for (auto dir : dirs) {
                    int ii = i + dir[0], jj = j + dir[1];
                    if (ii<0 || ii>=m || j<0 || j>n || word[current+1] != board[ii][jj]) continue;
                    if (search(ii,jj,word,current+1,board,m,n,len)) return true;
                }
                board[i][j] = c;
                return false;
            }
        }
        bool exist(vector<vector<char>>& board, string word) {
            int m = board.size(), n = board[0].size(), len = word.length();
            for (int i = 0; i < m;i++) {
                for (int j = 0; j < n ;j++) {
                    if (board[i][j] == word[0] && search(i, j, word,0,board, m, n, len))  return true;
                }
            }
            return false;
        }
    };
    

    Of course, in the beginning I used a vector<vector<bool>>& visited to log all those visited then I changed it to see whether speed boosts. But apparently this doesn't make any changes doesn't. Just so confused why my solution is SOOOO SLOW despite of I used same idea that lots of quick solution uses? Anyone have any thoughts??? Any hint will be appreciated :)


  • 1
    H

    I was able to reduce the run time of your solution by more than half just by creating the dirs vector only once and passing it to the search function. The run time is 164 ms.

    class Solution {
    public:
        bool search(int i, int j, string& word, int current, vector<vector<char>>& board, int& m, int& n, int& len, vector<vector<int>>& dirs) {
            if (current == len - 1 && word[current] == board[i][j]) {
                return true;
            }
            else {
                char c = board[i][j];
                board[i][j] = '*';
                for (auto dir : dirs) {
                    int ii = i + dir[0], jj = j + dir[1];
                    if (ii<0 || ii>=m || j<0 || j>n || word[current+1] != board[ii][jj]) continue;
                    if (search(ii,jj,word,current+1,board,m,n,len, dirs)) return true;
                }
                board[i][j] = c;
                return false;
            }
        }
        bool exist(vector<vector<char>>& board, string word) {
            vector<vector<int>> dirs = {{-1,0},{1,0},{0,-1},{0,1}}; //Up, down,left,right
            int m = board.size(), n = board[0].size(), len = word.length();
            for (int i = 0; i < m;i++) {
                for (int j = 0; j < n ;j++) {
                    if (board[i][j] == word[0] && search(i, j, word,0,board, m, n, len, dirs))  return true;
                }
            }
            return false;
        }
    };
    

    Even I had extremely high runtimes at the beginning. But the culprit was recursion parameters, the more the params the more time it takes to push and pop from the system stack. I went ahead and got rid of the dirs vector and for loop and hard coded the 4 possible directions and the run time now goes down to a whopping 16 ms! The code is here.

    class Solution {
    public:
        bool search(int i, int j, string& word, int current, vector<vector<char>>& board, int& m, int& n, int& len) {
            if (current == len - 1 && word[current] == board[i][j]) {
                return true;
            }
            else {
                char c = board[i][j];
                board[i][j] = '*';
                int ii = i + 1, jj = j;
                if (! (ii<0 || ii>=m || j<0 || j>n || word[current+1] != board[ii][jj])){
                    if (search(ii,jj,word,current+1,board,m,n,len)) return true;
                }
                ii = i, jj = j + 1;
                if (! (ii<0 || ii>=m || j<0 || j>n || word[current+1] != board[ii][jj])){
                    if (search(ii,jj,word,current+1,board,m,n,len)) return true;
                }
                ii = i - 1, jj = j;
                if (! (ii<0 || ii>=m || j<0 || j>n || word[current+1] != board[ii][jj])){
                    if (search(ii,jj,word,current+1,board,m,n,len)) return true;
                }
                ii = i, jj = j - 1;
                if (! (ii<0 || ii>=m || j<0 || j>n || word[current+1] != board[ii][jj])){
                    if (search(ii,jj,word,current+1,board,m,n,len)) return true;
                }
                board[i][j] = c;
                return false;
            }
        }
        bool exist(vector<vector<char>>& board, string word) {
            int m = board.size(), n = board[0].size(), len = word.length();
            for (int i = 0; i < m;i++) {
                for (int j = 0; j < n ;j++) {
                    if (board[i][j] == word[0] && search(i, j, word,0,board, m, n, len))  return true;
                }
            }
            return false;
        }
    };
    

  • 1
    M

    @harunrashidanver Thank you so much for pointing this out, it helps me a lot! :)


  • 1
    H

    @mugua-stolaf No problem! It's amazing how it happens behind the scene! Happy hacking :)


  • 1
    A

    I think to use recursive function is a big problem to performance and to scalability.


  • 0
    M

    @amorzh-hotmail-com yeah you're absolutely right. Despite of time spent on recursive call/pop the stack, the space consumed is also a big hurt :/


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.