My C++ solution takes 88 ms, is there something wrong? how to enhance?


  • 0
    H
    bool exist(vector<vector<char>>& board, string word) {
        if (0 == word.length()) return false;
        if (0 == board.size()) return false;
        if (0 == board[0].size()) return false;
        
        int row = board.size(), col = board[0].size(), size = word.length();
        
        vector<int> wordRow(word.length(), 0);
        vector<int> wordCol(word.length(), 0);
        
        bool found = false;
        char c = word[0];
        for (int i=0; i<row; ++i) {
            for (int j=0; j<col; ++j) {
                if (c == board[i][j]) {
                    int idx = 0;
                    wordRow[idx] = i;
                    wordCol[idx] = j;
                    found = find(board, row, col, word, wordRow, wordCol, idx + 1, size);
                }
                if (found) break;
            }
            if (found) break;
        }
        
        return found;
    }
    
    bool find(vector<vector<char>>& board, int row, int col, string& word, vector<int>& wordRow, vector<int>& wordCol, int idx, int size) {
        if (idx == size) return true;
        
        int prevRow = wordRow[idx-1];
        int prevCol = wordCol[idx-1];
        
        bool found = false;
        if (!found && prevRow+1 < row && board[prevRow+1][prevCol] == word[idx] &&
            !isCircle(word, wordRow, wordCol, prevRow+1, prevCol, idx)) {
            found = find(board, row, col, word, wordRow, wordCol, idx + 1, size);
        }
        if (!found && prevRow-1 >= 0  && board[prevRow-1][prevCol] == word[idx] &&
            !isCircle(word, wordRow, wordCol, prevRow-1, prevCol, idx)) {
            found = find(board, row, col, word, wordRow, wordCol, idx + 1, size);
        }
        if (!found && prevCol+1 < col && board[prevRow][prevCol+1] == word[idx] &&
            !isCircle(word, wordRow, wordCol, prevRow, prevCol+1, idx)) {
            found = find(board, row, col, word, wordRow, wordCol, idx + 1, size);
        }
        if (!found && prevCol-1 >= 0  && board[prevRow][prevCol-1] == word[idx] &&
            !isCircle(word, wordRow, wordCol, prevRow, prevCol-1, idx)) {
            found = find(board, row, col, word, wordRow, wordCol, idx + 1, size);
        }
        
        return found;
    }
    
    inline bool isCircle(string& word, vector<int>& wordRow, vector<int>& wordCol, int r, int c, int idx) {
        bool circle = false;
        for (int i=0; i<idx; ++i) {
            if (word[i] == word[idx]) {
                if (wordRow[i] == r && wordCol[i] == c) {
                    // There is a cycle, break;
                    circle = true;
                    break;
                }
            }
        }
        if (!circle) {
            wordRow[idx] = r;
            wordCol[idx] = c;
        }
        return circle;
    }

  • 0
    H

    using a hash array (row*col) to store the previous checked point on the board instead of searching the previous items, make this solution as 16 ms.


  • 0
    H
    // 16 ms
    bool exist(vector<vector<char>>& board, string word) {
        if (0 == word.length()) return false;
        if (0 == board.size()) return false;
        if (0 == board[0].size()) return false;
        
        int row = board.size(), col = board[0].size(), size = word.length();
        
        vector<int> boardCheck(row*col, 0);
        
        bool found = false;
        char c = word[0];
        for (int i=0; i<row; ++i) {
            for (int j=0; j<col; ++j) {
                if (c == board[i][j]) {
                    int point = i*col+j;
                    boardCheck[point] = 1;
                    found = find(board, row, col, word, boardCheck, i, j, 1, size);
                    boardCheck[point] = 0;
                }
                if (found) break;
            }
            if (found) break;
        }
        
        return found;
    }
    
    bool find(vector<vector<char>>& board, int row, int col, string& word, vector<int>& boardCheck, int prevRow, int prevCol, int idx, int size) {
        if (idx == size) return true;
        int idx1 = idx+1;
        
        bool found = false;
        if (!found && prevRow+1 < row && board[prevRow+1][prevCol] == word[idx]) {
            int point = (prevRow+1)*col+prevCol;
            if (0 == boardCheck[point]) {
                boardCheck[point] = 1;
                found = find(board, row, col, word, boardCheck, prevRow+1, prevCol, idx1, size);
                boardCheck[point] = 0;
            }
        }
        if (!found && prevRow-1 >= 0  && board[prevRow-1][prevCol] == word[idx]) {
            int point = (prevRow-1)*col+prevCol;
            if (0 == boardCheck[point]) {
                boardCheck[point] = 1;
                found = find(board, row, col, word, boardCheck, prevRow-1, prevCol, idx1, size);
                boardCheck[point] = 0;
            }
        }
        if (!found && prevCol+1 < col && board[prevRow][prevCol+1] == word[idx]) {
            int point = prevRow*col+prevCol+1;
            if (0 == boardCheck[point]) {
                boardCheck[point] = 1;
                found = find(board, row, col, word, boardCheck, prevRow, prevCol+1, idx1, size);
                boardCheck[point] = 0;
            }
        }
        if (!found && prevCol-1 >= 0  && board[prevRow][prevCol-1] == word[idx]) {
            int point = prevRow*col+prevCol-1;
            if (0 == boardCheck[point]) {
                boardCheck[point] = 1;
                found = find(board, row, col, word, boardCheck, prevRow, prevCol-1, idx1, size);
                boardCheck[point] = 0;
            }
        }
        
        return found;
    }
    

Log in to reply
 

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