Why is this code timing out (similar to some java solution posted)


  • 0
    P
    class Solution {
    public:
    
        bool search(int x,int y, vector<vector<char> > b, string word,int index)
        {
                if(index == word.size()) return true;
                if(x < 0 || y < 0 || x >= b.size() || y >= b[0].size())
                        return false;
                char ch = b[x][y];
                if(ch != word[index])return false;
                
                int dir_x[] = {1,-1,0,0};
                int dir_y[] = {0,0,1,-1};
                bool increased = false;
                b[x][y]-= 26;
                for(int i=0;i<4;i++)
                {
                    int new_x = x + dir_x[i];
                    int new_y = y + dir_y[i];
                    if(new_x < 0 || new_y < 0 || new_x >= b.size() || new_y >= b[0].size())continue;
                    increased |= search(new_x,new_y,b,word,index+1);
                }
                b[x][y]+= 26;
                return increased;
        }
        bool exist(vector<vector<char> > &board, string word) {
            bool solve = false;
            for(int i = 0;i<board.size();i++)
                for(int j=0;j<board[i].size();j++)
                        if(search(i,j,board,word,0))return true;
                    
            return false;
        }
    };
    

    I am wondering why is the above code timing out. A similar java approach seems to be working fine and within time limits.

    Any suggestions?


  • 0
    L

    Doesn't seem like you're checking if a specific character has already been used.


Log in to reply
 

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