Time Limit Exceeded using DFS


  • -2
    A
    public class Solution {
    public boolean exist(char[][] board, String word) {
        //as we are search for a word
        //we can use a bfs method 
        if(board.length==0||board[0].length==0) return false;
        
        int row = board.length;
        int col = board[0].length;
        
        Boolean result = false;
        int wordLength = word.length();
        
        //in this case
        boolean[][] checkTable = new boolean[row][col];
        
        
        //as we know the depth which is the length of string 
        //we can use dfs with constrain 
        for(int r=0;r<row;r++){
            for(int c=0;c<col;c++){
                //checktable
                for(int i=0;i<row;i++){
                    for(int j=0;j<col;j++){
                        checkTable[i][j] =false;
                    }
                }
                //begin of dfs
                dfs(0,wordLength,checkTable,board,word,r,c,result,row,col);
                if(result) return true;
            }
        }
        
        return result;
    }
    
    public void dfs(int step,int wordLength,boolean[][] checkTable,char[][] board, String word,int r,int c,Boolean result,int maxRow,int maxCol){
        if(step==wordLength-1 && word.charAt(step)==board[r][c]){
            result = true;
            return;
        }
        else if(step>wordLength-1){
            return;
        }
        
        if(word.charAt(step)==board[r][c] && !result){
                for(int tmpR = -1;tmpR<2;tmpR+=2){
                    if(r-tmpR >=0 && r-tmpR<maxRow && !checkTable[r-tmpR][c]){
                        checkTable[r-tmpR][c] = true;
                        if(board[r-tmpR][c] == word.charAt(step+1)){
                            dfs(step+1,wordLength,checkTable,board,word,r-tmpR,c,result,maxRow,maxCol);
                        }
                        checkTable[r-tmpR][c] = false;
                    }
                }
                
                 for(int tmpC = -1;tmpC<2;tmpC+=2){
                    if(c-tmpC >=0 && c-tmpC<maxCol && !checkTable[r][c-tmpC]){
                        checkTable[r][c-tmpC] = true;
                        if(board[r][c-tmpC] == word.charAt(step+1)){
                            dfs(step+1,wordLength,checkTable,board,word,r,c-tmpC,result,maxRow,maxCol);
                        }
                        checkTable[r][c-tmpC] = false;
                    }
                }
                
        }
        
        
        
    }
    

    }

    My approach for this question is using recursion and DFS. Each character in the char[][] board will serve as a starting point for the DFS. For each new starting point I will initialize the chechTable which is used to record the chosen character along DFS. The DFS will stop when it reach the depth which is equal to the length of the word.

    Last executed input is a very big matrix ....I think I am so close to the answer...

    Hi everyone, I found the problem of my code. It's simple and stupid. I passed the 'boolean result' into the function while boolean is immutable class just like integer. I change the boolean result to Arraylist boolean result, and the TLE problem went away.


  • 0

    Please refrain from pasting the whole test case here, it is not useful to debug your code. Please explain the approach of your code briefly so others can help you.


  • 0
    4

    Hi, I use DFS, similar to this post: http://yucoding.blogspot.com/2013/02/leetcode-question-124-word-search.html
    but also got "Time Limit Exceeded" (even when I copied the code in that post, still got that message)


  • 0
    M

    I think dfs + kmp will be faster. But I did not get AC right now.


  • 0
    Y

    Yes, my version of DFS solution also get TLE for the case ["elxllvxegzmvgnhrypvagxrgwktiqnyuavfnsfsbgewnrferubrcykjwveenrfhtamhvtzwafspzxvqtwkxwwgttkzgdenzhcgcvhyxosonrjgmhsjeo","qxkcyqidehkipofwofmgtazfilocwuqotatstbvzkhhzvmxjrjrnlsutdixbdoqwqjolklkwstvpgsyzdropjikoriquygsqphcbuoxniucoodpruegg","mrudzkzxsupjbrmxgjkofpetutnoztwmmrrndtmwncfqtsnbdaplrvglptbqpycdpwrspdqehyudsjevjwictpnkkpbznfdebwysbpwjnsmfcscnqnqk","cdumuvojbtnepmxqdvbsopzskdfaqxkudhhxexhfqwkfkjxnezhuqgmamsbcrnxuwgsbdbgtxsaidxxiyfcplrpxlqccgzxchrdksmfpgfxkexudcysp","phnaarfisckztqllcqckxcubzqebpyqgifjkwosqqeplucyysajreftfwzgnazvkgeufsovisnvpptnkwybagwgeyotypokwteblsywmlrbbnrljrmlx","ltbjiujxjtvczwprvlfifhjsaubrjmpugsfqnopyjlcijrbgfgpkpacpvfhgtwczohrdxhbgudqfxroczdopdqeavliojkqarjdqshwomoujfinhnbws","tatoobfxmxzfidwbkupwjlgqtvxgxvzqyuhmxollnltvqpyalowwbepvcmdzkeriaauyohjducbktzkhpjdrpsorhrstykbykxwbeigzmhlihwpwhupw","pdoyxirvsuvfrsivcowqwiydgpbnmrlbwbbtkuqcomjfgrckgbaejzjrqkgcdrfctgxfcojqctvkkausbuymvhdmsjqxcwzxezchnmzrfxbrxvmapkmn","srbmcrleplcukgdzscszbtraofafpmujdvxfnjmcwoygubhpgzojuhkkmkrexmnchlkuuwzqmxyibhxhioqcvcmindmmrbozoyvkwuciscrvlqcteuxa","zlkmryyibmhqndcjzfutjnovdsokpomozyaqwyzxmipbnslnxhgguxbzpslegxsfxuytuztjhikvaxkzesgypjahdllllgticrexqxgzfqwiqghubpvq","bxxeilsvtleveksuhatotswjygfzvasyxrficxdvijtmtniaodrhvnswtxvrappxhuhjtlhduarqnzsdfjmcxeyscwlcldbszjetwnwspoiepbiukuzj","zxedtrfhuiburhpnulilbqqttypgsoptmvwhnbqhmuddbstygbjjtzcnzstsiknwgkgvnwczqgfuyysgbdqwfslemgyvrmtzwzujwyjoeqifoclrgdnl","ybrkhqhycbzyatjysspyizfycrrkwhxuiofpeoogrpeujosdijbtjhtlalxwsutciarpohvgxcaisulcgovpvrcxezwyvpafprufzqlysngmkroqfkfd","djchkyhfphkeafkbxxzrnfdxyrngdulgfnppowufdgkgnwhkvhbiogfpyuxdqkkvzbknygtdnfjadtnaaojqvqhvleydokzomldmsyrhfbhkuulwluoi","mwfzcddtoejcpmojnfqsiafewqchmtrypwytcdmqhxuwmkizrytcaygxqlgceabvwboyedqnamlowtnoujqujytajacnafkyizxoepbgcnvygkoatgxf","fqfqsjgsrqtzrsoxhpgjcbklnaljhkoobvetemovfjxwblwiccuffgssgddnqrbrmimtwcobllamywvbargfxyzdddttwwmjgbcddsgpegbeeyfernlo","nlutqnomlbxsczvhubwakaeoakvsxgiltcejrswdvtxzvshpvdrhfvygftafbisvnyeeqcjoygntawkycbfhwdpeyplaadvnbbttgdhelxzmtjkxmrfk","xwovozvocsdfwwzcbigphfbbqnacgfmdedbsewgjrjonhprlyzafediwsjyyqmeurfmwdufufvjnlcalbaqhfbdxkdxaqbxjgjfkgmglisavuagwcydh","zjglmeoeflomwtycigosyqnvrvttvydvhjgupwyvhmjgijiqpykqpzliugdpegmmsvihriezvnhfwpxoqhefgrpcxstbzgptbxaugfvduckrujhkqlry","cgcbyvczdusgttbbaweubqnvzufrfypjetkcrpcujwbcpeepakmddzycufubdlnhhzmyoqszmveezkvcwhfzheedjygnltwstiqjallngptizokxyrxh","vbkhbswomujhfbqfmduvsndtenrceojcrvlsnjizdriitbofekcxafseujgbzrdsmqmzzvbcmjlfkbnpnponvgrrszsrqxkcnwcmtdrgoenbfaquqgin","obegbxatumwkkawefpmvtzwaamvsudfjglrhirbffzpqbnwididyhazhowbjbguhslrcfujmtaewoaetkhtshsbwqdhrldzfqqixktkfuodkrhfboyvy","tzwjcfdpicvyufwgyinsyqcpxjtnioldnjmropjwtexnjvvjdicbygtxsmlacydsirlyjuxcausjrnvuyzxyhqwzehbhhebrymqhhnljjdvatqwtptrw","kpyqyzzggaxenpnwcyfneanzsjshdlgpbefzdhfjhfpuucszbamfcagvjycojkfmonmuurfbyvytxssysefvglqslugxfmjtbvpvpvypqwinpcohjtep","huhuporucbpfyfapayfsxpfostvbpcqywysnomjspbxnizfkxmcwbhktdiwukpuinmwdahxpiufqtkaswepxmbtrjrntghettcywjvlurqmkapfytwyh","xtyhklcruimqklmuixoaoamqprrlppsnitwsgalbjyrtldntadvqgijxbairpbgzwctccfdndwhozwjcafuipdfqdojurptptpryuxlztspvraztftbw","xipawyxpqqgjhyhbxvcsprpguozbicyhlpjjngbfzhrghakgvmzlgotafvbpxbwiqfugovlneetmfdscstnyijapebebdamthibxdnkhrgvylobdhqdr","zdgdhmhmmvfwdhtiwgpponozbrfkhkehommxzvjnqojvxfdvnvnbibclujxbubkiqzhpuqcngoievobijolrrnelxbptfzdvykkvaoigesmzgojpcwiw","....], "oajgdkcokvfpdaslnmomrpgwitwdoku"


  • 5
    E

    I passed it with a non-recursive DFS. Follow possible paths only and backtrack when meet a dead end.

    class Solution {
    public:
        bool exist(vector<vector<char> > &board, string word) {
            
        int row = board.size();
        
        if (row == 0 || word.size() == 0)
            return false;
            
        int col = board[0].size();
        stack<pair<int, int>> stk;
        
        for (int i = 0; i < board.size(); ++i)
            for (int j = 0; j < board[i].size(); ++j) {
                
                if (board[i][j] == word[0])
                    stk.push(make_pair(i * col + j, 0));
                
                while (!stk.empty()) {
                    int n = stk.top().first;
                    int x = n / col;
                    int y = n % col;
                    int pos = stk.top().second;
                    
                    if (~board[x][y] & 0x80) {
                        
                        if (board[x][y] == word[pos] ) {
                            if (pos == word.size() - 1)
                                return true;
                            
                            board[x][y] |= 0x80;
                            
                            if (x - 1 >= 0 && (~board[x - 1][y] & 0x80))
                                stk.push(make_pair((x - 1) * col + y, pos + 1));
                            if (x + 1 < row && (~board[x + 1][y] & 0x80))
                                stk.push(make_pair((x + 1)* col + y, pos + 1));
                            if (y - 1 >= 0 && (~board[x][y - 1] & 0x80))
                                stk.push(make_pair(x * col + y - 1, pos + 1));
                            if (y + 1 < col && (~board[x][y + 1] & 0x80))
                                stk.push(make_pair(x * col + y + 1, pos + 1));
                        } else {
                            stk.pop();    
                        }
                    } else {
                        stk.pop();
                        board[x][y] &= ~0x80;
                    }
                }
            }
            
        return false;
        }
    };
    

  • 0
    P

    I am wondering what is 0x80?


  • 0
    P

    Never mind. I understood now. So, it is to mark already used in itself. Because a - Z maximum is represented by only number 90


Log in to reply
 

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