Concise but efficient in C, well-commented


  • 1
    bool isFound(char** board, int row, int col, char*word, int rIndex, int cIndex)
    {
        if(*word == '\0') return true; //reach it end;
        if(rIndex>=row || cIndex>=col || rIndex<0 || cIndex<0 || *word!=board[rIndex][cIndex]) return false;
        char t = board[rIndex][cIndex];
        board[rIndex][cIndex] = '\0'; //avoid re-visiting;
        if(isFound(board, row, col, word+1, rIndex+1, cIndex) || 
           isFound(board, row, col, word+1, rIndex-1, cIndex) || 
           isFound(board, row, col, word+1, rIndex, cIndex+1) || 
           isFound(board, row, col, word+1, rIndex, cIndex-1)) 
                 return true;
        board[rIndex][cIndex] = t; //restore to the original;
        return false; //if all failed, return false;
    }
    
    bool exist(char** board, int row, int col, char* word) 
    {
        //Start from each position;
        for(int i = 0; i < row; i++)
            for(int j = 0; j < col; j++)
                if(isFound(board, row, col, word, i, j))
                    return true;
        return false;
    }

  • 0

    Got too many characters in one line! Not convenient.


  • 0

    @jedihy You are right, updated now. Thanks!


  • 1

    Related C++ solution:

    class Solution {
        int rowSize, colSize, len;
        const char HOLDER = '#';
        bool traverse(vector<vector<char>>& board, int r, int c, string& path, string& word){
            if(path.length() == len) return path == word;
            if(r==-1 || r==rowSize || c==-1 || c==colSize || board[r][c]==HOLDER) return false;
            char a = board[r][c];
            if(word[path.length()] != a) return false;
            board[r][c] = HOLDER;
            path += a;
            if(traverse(board, r-1, c, path, word) ||
                traverse(board, r+1, c, path, word) ||
                traverse(board, r, c-1, path, word) ||
                traverse(board, r, c+1, path, word)) return true;
            path.pop_back();
            board[r][c] = a;
            return false;
        }
    public:
        bool exist(vector<vector<char> > &board, string word) {
            rowSize = board.size(), colSize = rowSize? board[0].size() : 0, len = word.length();
            string path = "";
            for(int r = 0; r < rowSize; ++r)
                for(int c = 0; c < colSize; ++c)
                    if(traverse(board, r, c, path, word)) return true;
            return false;
        }
    };
    

  • 2

    Re-code the above C solution and achieved the best submission in C++.

    class Solution {
        int rowSize, colSize, len;
        const char HOLDER = '#';
        bool traverse(vector<vector<char>>& board, int r, int c, string& word, int pos){
            if(pos == len) return true;
            if(r==-1 || r==rowSize || c==-1 || c==colSize || word[pos]!=board[r][c]) return false;
            char a = board[r][c];
            board[r][c] = HOLDER;
            if(traverse(board, r-1, c, word, pos+1) ||
                traverse(board, r+1, c, word, pos+1) ||
                traverse(board, r, c-1, word, pos+1) ||
                traverse(board, r, c+1, word, pos+1)) return true;
            board[r][c] = a;
            return false;
        }
    public:
        bool exist(vector<vector<char> > &board, string word) {
            rowSize = board.size(), colSize = rowSize? board[0].size() : 0, len = word.length();
            for(int r = 0; r < rowSize; ++r)
                for(int c = 0; c < colSize; ++c)
                    if(traverse(board, r, c, word, 0)) return true;
            return false;
        }
    };
    

  • 0
    W

    @LHearen Hi, this is my solution,nearly same idea with yours.Why it`s 860ms??

    class Solution {
    public:
        vector<vector<char>> board;
        int n;
        string word;
        bool exist(vector<vector<char>>& boar, string wor) {
            word=wor; board=boar;
            int I=board.size();   n=word.size()-1;
            int J=board[0].size();
           
            vector<vector<bool>> visit(I,vector<bool>(J,true));
        
            for(int i=0;i<I;i++){
                for(int j=0;j<J;j++){
                    if(board[i][j]==word[0]){
                        if(helper(visit,i,j,0,I,J))  \\find the first
                        return true;
                    } 
                }
            }
            return false;
        }
        
        bool helper(vector<vector<bool>>visit ,int i,int j,int w,int I,int J){
            if(i>=I||j>=J) return false;
            visit[i][j]=false;
            if(w==n) return true;
            if(j+1<J&&board[i][j+1]==word[w+1]&&visit[i][j+1]&&helper(visit,i,j+1,w+1,I,J)) return true;
            if(i+1<I&&board[i+1][j]==word[w+1]&&visit[i+1][j]&&helper(visit,i+1,j,w+1,I,J)) return true;
            if(i>0&&board[i-1][j]==word[w+1]&&visit[i-1][j]&&helper(visit,i-1,j,w+1,I,J)) return true;
            if(j>0&&board[i][j-1]==word[w+1]&&visit[i][j-1]&&helper(visit,i,j-1,w+1,I,J)) return true;
            visit[i][j]=true;
            return false;
        }
    };
    

  • 0

    @wxfang_4010 I think there can be two major reasons:

    • C++ is slower than C especially when it comes to built-in higher-level objects like vector;
    • your checking and traversing code is more complicated, though normally it's okay but when there are lots of them, it can be the bottleneck.

Log in to reply
 

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