I can't believe only 9ms and beats 92%


  • 0
    D

    any question??? please @me

    class Solution {
    public:
        //start = j*n+i; k = the kth digit in word; direc = 1,2,3,4,0:the direction from left,right,up,down,begin(no)
        bool helper(vector<vector<char>>& board, string &word, int start, int k, int direc){
            if(k+1 == word.size()) return true;
            int m = board.size();
            int n = board[0].size();
            int j = start/n;
            int i = start%n;
            if(direc != 3 && j>0 && board[j-1][i] == word[k+1]){
                char tmp = board[j-1][i];
                board[j-1][i] = ' ';
                if(helper(board,word,(j-1)*n+i,k+1,4)) return true;
                board[j-1][i] = tmp;
            }
            if(direc != 4 && j<m-1 && board[j+1][i] == word[k+1]){
                char tmp = board[j+1][i];
                board[j+1][i] = ' ';
                if(helper(board,word,(j+1)*n+i,k+1,3)) return true;
                board[j+1][i] = tmp;
            }
            if(direc != 1 && i>0 && board[j][i-1] == word[k+1]){
                char tmp = board[j][i-1];
                board[j][i-1] = ' ';
                if(helper(board,word,j*n+i-1,k+1,2)) return true;
                board[j][i-1] = tmp;
            }
            if(direc != 2 && i<n-1 && board[j][i+1] == word[k+1]){
                char tmp = board[j][i+1];
                board[j][i+1] = ' ';
                if(helper(board,word,j*n+i+1,k+1,1)) return true;
                board[j][i+1] = tmp;
            }
            return false;
        }
        bool exist(vector<vector<char>>& board, string word) {
            int m = board.size();
            int n = board[0].size();
            if(word.size()>m*n) return false;
            for(int i=0;i<m*n;++i)
                if(board[i/n][i%n] == word[0]){
                    char tmp = board[i/n][i%n];
                    board[i/n][i%n] = ' ';
                    if(helper(board,word,i,0,0)) return true;
                    board[i/n][i%n] = tmp;
                }
            return false;
        }
    };

Log in to reply
 

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