LeetCode 212. Word Search II C++纯DFS AC

class Solution {
public:
    
    int row, col, nwords;
    vector<string> ans;
    
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        row = board.size(), nwords = words.size();
        if (words.size() == 0) return ans;
        if (row == 0) return ans;
        col = board[0].size();
        if (col == 0) return ans;
        
        sort(words.begin(), words.end());
        
        for (int i = 0; i < nwords; ++i){
            bool inAns = false;
            if (i >= 1 && words[i] == words[i - 1]) continue;
            
            for (int j = 0; j < row && !inAns; ++j){
                for (int k = 0; k < col && !inAns; ++k){
                    if (board[j][k] == words[i][0]){
                        vector<vector<bool>> flag(row, vector<bool>(col, 0));
                        if (isTrue(board, flag, j, k, 0, words[i])){
                            ans.push_back(words[i]);
                            inAns = true;
                        }
                    }
                }
            }
        }
        
        return ans;
    }
    
    bool isTrue(vector<vector<char>>& board, vector<vector<bool>> &flag, int x, int y, int cur, string word){
        if (cur == word.size() - 1){
            return true;
        }

        flag[x][y] = true;
        int a = false, b = false, c = false, d = false;
        
        if (x - 1 >= 0 && board[x - 1][y] == word[cur + 1] && flag[x - 1][y] == false){
            if (isTrue(board, flag, x - 1, y, cur + 1, word)){
                return true;
            }
        }

        if (x + 1 < row && board[x + 1][y] == word[cur + 1] && flag[x + 1][y] == false){
            if(isTrue(board, flag, x + 1, y, cur + 1, word)){
                return true;
            }
        }

        if (y - 1 >= 0 && board[x][y - 1] == word[cur + 1] && flag[x][y - 1] == false){
            if(isTrue(board, flag, x, y - 1, cur + 1, word)){
                return true;
            }
        }  

        if (y + 1 < col && board[x][y + 1] == word[cur + 1] && flag[x][y + 1] == false){
            if(isTrue(board, flag, x, y + 1, cur + 1, word)){
                return true;
            }
        }   

        flag[x][y] = false;

       return false;
    }
};
已邀请:

要回复问题请先登录注册

返回顶部