0

Here is the problem of leetcode. Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of a sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

I simply did dfs with keeping the check on the length of the word given.

class Solution {

    public:

        int n,m;
        bool check(int i,int j){
            if(i<0||j<0||i>=n||j>=m)return false;
            return true; 
        }

        int ans;

    void dfs(vector<vector<char>>& board,string word,int i,int j,int k){       

        if(!check(i,j) || board[i][j]!=word[k] || board[i][j]=='*')return  ;

        char x=board[i][j];
        board[i][j]='*';

        if(k==word.length()-1){
            ans=1;
            return ;
        }

        //cout<<s<<endl;

        dfs(board,word,i+1,j,k+1);
        dfs(board,word,i-1,j,k+1);
        dfs(board,word,i,j+1,k+1);
        dfs(board,word,i,j-1,k+1);

        board[i][j]=x;

    }
    bool exist(vector<vector<char>>& board, string word) {
        n=board.size();m=board[0].size();
        ans=0;
        int k=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                dfs(board,word,i,j,k);
                if(ans==1)return true;
            }
        }
        return ans;
    }
};

TLE for the given input: https://leetcode.com/submissions/detail/243435697/testcase/

Himank Kansal
  • 21
  • 5
  • Hint: Think if you can apply DP or may be you can apply Trie. – Shridhar R Kulkarni Jul 15 '19 at 04:28
  • @ShridharRKulkarni Applying Trie for a single word would result in the same complexity I think since I am checking before entering whether the 'kth' letter of the board in use is the same as a word's 'kth' letter or not. – Himank Kansal Jul 15 '19 at 04:32
  • Code works, but is too slow? Give [Code Review's how to ask section a read](https://codereview.stackexchange.com/help/asking) and then consider asking there. It's generally a better place for "How do I make my code work better?" type questions. – user4581301 Jul 15 '19 at 04:35
  • Note: due to low spatial locality, `vector>` can sometimes be an unexpected boat anchor. – user4581301 Jul 15 '19 at 04:38
  • Note: `exist` calls `dfs` `m`x`n` times. After that you have `dfs` recursing. That's pretty expensive. – user4581301 Jul 15 '19 at 04:42
  • @user4581301 But I don't have options right? I have to check for every cell and then do dfs from there. Please tell me if you have a better approach to work with. – Himank Kansal Jul 15 '19 at 04:45
  • `word` should be passed by `const &`. – Sid S Jul 15 '19 at 05:03
  • Consider: do you have to keep searching after you find the word? – 1201ProgramAlarm Jul 15 '19 at 05:06
  • Adding & helped to increase the efficiency, also I had to stop searching whenever I found the word. But can anyone explain to me why adding '&' before word helped? – Himank Kansal Jul 15 '19 at 05:24
  • The thing with these sorts of questions is there is always some sneaky trick you can use to reduce the work load. I haven't looked at the problem and maybe you've already found the trick and the program is just brutal, but N-squared in a competitive programming problem is often the kiss of death. `&` helped by reducing the number of times `word` was copied. See [What's the difference between passing by reference vs. passing by value?](https://stackoverflow.com/questions/373419/whats-the-difference-between-passing-by-reference-vs-passing-by-value) – user4581301 Jul 15 '19 at 15:10

0 Answers0